DFS—SEARCH

搜索策略与信息检索

题目描述

年少的拉尔夫出于玩笑心态，从一个小镇盗走了一辆汽车，然而他并未意识到这辆车实际上属于警局，并且车辆上安装了一种用于追踪行驶轨迹的设备。该设备因年代久远，仅能传输车辆移动的大致方向信息。

需要编写一个程序，借助小镇的地图协助警方定位该车辆。程序需能够展示出车辆在行驶过程中可能抵达的所有最终位置。

地图呈现为矩形结构，其中使用特定符号标识可通行与不可通行区域。符号 \verb!.! 表示该区域允许车辆通行，而 \verb!X! 则表示此地无法通行。拉尔夫驾驶的汽车初始位置由 \verb!*! 标识，并且车辆可以从该起点出发移动。

汽车具备四个方向的移动能力：北（向上）、南（向下）、西（向左）以及东（向右）。

拉尔夫的行驶路径由一系列预设的方向指令所描述，在每一个指令下，他驾驶车辆通过小镇中一个或多个允许通行的区域。

输入格式

输入文件的首行由两个通过空格分隔的自然数 R 与 C 构成，其中 1\le R\le 50，1\le C\le 50，分别用于表示小镇地图中的行数与列数。

随后的 R 行中，每一行均包含 C 个符号（\verb!.!、\verb!X! 或 \verb!*!），这些符号用于描述地图对应位置的信息。

在第 R+2 行中，