年轻的拉尔夫开玩笑地从一个小镇上偷走了一辆车，但他没想到的是那辆车属于警察局，并且车上装有用于发射车子移动路线的装置。

那个装置太旧了，以至于只能发射关于那辆车的移动路线的方向信息。

编写程序，通过使用一张小镇的地图帮助警察局找到那辆车。程序必须能表示出该车最终所有可能的位置。

小镇的地图是矩形的，上面的符号用来标明哪儿可以行车哪儿不行。“.”表示小镇上那块地方是可以行车的，而符号“X”表示此处不能行车。拉尔夫所开小车的初始位置用字符的“*”表示，且汽车能从初始位置通过。

汽车能向四个方向移动：向北(向上)，向南(向下)，向西(向左)，向东(向右)。

拉尔夫所开小车的行动路线是通过一组给定的方向来描述的。在每个给定的方向，拉尔夫驾驶小车通过小镇上一个或更多的可行车地点。

输入文件的第一行包含两个用空格隔开的自然数R和C，1≤R≤50，1≤C≤50，分别表示小镇地图中的行数和列数。

以下的R行中每行都包含一组C个符号(“.”或“X”或“*”)用来描述地图上相应的部位。

接下来的第R+2行包含一个自然数N，1≤N≤1000，表示一组方向的长度。

接下来的N行幅行包含下述单词中的任一个：NORTH(北)、SOUTH(南)、WEST(西)和EAST(东)，表示汽车移动的方向，任何两个连续的方向都不相同。

输出文件应包含用R行表示的小镇的地图(象输入文件中一样)，字符“*”应该仅用来表示汽车最终可能出现的位置。

4 5

.....

.X...

...*X

X.X..

3

NORTH

WEST

SOUTH

.....

*X*..

*.*.X

X.X..

 1     #include<stdio.h>   2     #include<iostream>   3     using namespace std;   4     const int MAX_N = 51;   5     const int MAX_M = 1001;   6     int R, C, N;   7     int x, y;   8     int turn[MAX_M];             //移动方向 ，turn[t] 表示 第t个方向    9     int M[MAX_N][MAX_N];         //以0，1存储原地图，方便判断   10     char A[MAX_N][MAX_N];        //以字符存储行驶后的地图，方便输出   11     int vis[MAX_N][MAX_N][MAX_M];    //vis[x][y][t] 表示 从点（x,y）往第t个方向（turn[t]）移动   12     void DFS(int x, int y, int t)  13     {  14         if (vis[x][y][t]) return;     //如果该移动状态出现过了，则不考虑   15         vis[x][y][t] = 1;             //没出现过，则考虑，标记。。   16         if (t > N)      //如果遍历完所有行驶方向，则得到一个目标可能点。  17         {  18             A[x][y] = ‘*‘;  19             return;  20         }  21         if (turn[t] == 1)            //北（上）  22         {  23             x--;                    //向上移动一步   24             while (x >= 1 && M[x][y])  //约束条件，一直行驶直到无法继续   25             {  26                 DFS(x, y, t + 1);   //从当前点开始搜索，按照turn的顺序行驶，每个方向都要走到边界   27                 x--;  28             }  29         }  30         if (turn[t] == 2)            //南（下）  31         {  32             x++;  33             while (x <= R && M[x][y])  34             {  35                 DFS(x, y, t+1);  36                 x++;  37             }  38         }  39         if (turn[t] == 3)                //西（左）   40         {  41             y--;  42             while (y >= 1 && M[x][y])  43             {  44                 DFS(x, y, t + 1);  45                 y--;   46             }   47         }                  48         if (turn[t] == 4)              //东（右）  49         {  50             y++;  51             while (y <= C && M[x][y])  52             {  53                 DFS(x, y, t + 1);  54                 y++;  55             }  56         }  57     }  58     int main()  59     {  60         int i, j;  61         cin>>R>>C;  62         for (i = 1; i <= R; i++)  63         {  64             for (j = 1; j <= C; j++)  65             {  66                 cin>>A[i][j];  67                 if (A[i][j] == ‘.‘) M[i][j] = 1;  68                 if (A[i][j] == ‘X‘) M[i][j] = 0;  69                 if (A[i][j] == ‘*‘)   70                 {  71                     A[i][j] = ‘.‘;  72                     M[i][j] = 1;  73                     x = i;  74                     y = j;  75                 }  76             }  77         }  78         cin>>N;  79         for (i = 1; i <= N; i++)  80         {  81             char dir[5];  82             cin>>dir;  83             if (dir[0] == ‘N‘) turn[i] = 1;                84             if (dir[0] == ‘S‘) turn[i] = 2;  85             if (dir[0] == ‘W‘) turn[i] = 3;  86             if (dir[0] == ‘E‘) turn[i] = 4;  87         }  88         DFS(x, y, 1);  89         for (i = 1; i <= R; i++)  90         {  91             for (j = 1; j <= C; j++)  92                 printf("%c", A[i][j]);  93             if(i != R)   94                 printf("\n");  95         }  96         return 0;  97     }

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<queue>  5 using namespace std;  6 const int MAXN=1001;  7 const int maxn=0x7fffffff;  8 int map[MAXN][MAXN];  9 int vis[MAXN][MAXN]; 10 int fx[MAXN]; 11 int n,m; 12 queue<int>xzb; 13 queue<int>yzb; 14 int p; 15 void bfs(int x,int y) 16 { 17     for(int l=1;l<=p;l++) 18     { 19      20         int sl=xzb.size(); 21         int will=fx[l];// 方向     22          23          if(will==1)    //1上 24          { 25              int nowx=xzb.front(); 26              int nowy=yzb.front(); 27              int wx=nowx-1; 28              int wy=nowy; 29              while(1) 30              { 31                  if(wx>=1&&wx<=n&&wy>=1&&wy<=m&&map[wx][wy]==0) 32                  { 33                      wx=wx-1; 34                      xzb.push(wx); 35                      yzb.push(wy); 36                  } 37                  else 38                  { 39                      if(l==p) 40                      map[nowx][nowy]=3; 41                      break; 42                  } 43             } 44             xzb.pop(); 45             yzb.pop(); 46          } 47          else if(will==2)// 2下 48          { 49              int nowx=xzb.front(); 50              int nowy=yzb.front(); 51              xzb.pop(); 52              yzb.pop(); 53              int wx=nowx+1; 54              int wy=nowy; 55              while(1) 56              { 57                  if(wx>=1&&wx<=n&&wy>=1&&wy<=m&&map[wx][wy]==0) 58                  { 59                      wx=wx+1; 60                      xzb.push(wx); 61                      yzb.push(wy); 62                  } 63                  else 64                  { 65                      if(l==p) 66                      map[nowx][nowy]=3; 67                      break; 68                  } 69             } 70             xzb.pop(); 71             yzb.pop(); 72          } 73          else if(will==3)// 3左 74          { 75              int nowx=xzb.front(); 76              int nowy=yzb.front(); 77              xzb.pop(); 78              yzb.pop(); 79              int wx=nowx; 80              int wy=nowy-1; 81              while(1) 82              { 83                  if(wx>=1&&wx<=n&&wy>=1&&wy<=m&&map[wx][wy]==0) 84                  { 85                      wy=wy-1; 86                      xzb.push(wx); 87                      yzb.push(wy); 88                  } 89                  else 90                  { 91                      if(l==p) 92                      map[nowx][nowy]=3; 93                      break; 94                  } 95             } 96             xzb.pop(); 97             yzb.pop(); 98          } 99          else if(will==4)//  4右 100          {101              int nowx=xzb.front();102              int nowy=yzb.front();103              xzb.pop();104              yzb.pop();105              int wx=nowx;106              int wy=nowy+1;107              while(1)108              {109                  if(wx>=1&&wx<=n&&wy>=1&&wy<=m&&map[wx][wy]==0)110                  {111                      wy=wy+1;112                      xzb.push(wx);113                      yzb.push(wy);114                  }115                  else116                  {117                      if(l==p)118                      map[nowx][nowy]=3;119                      break;120                  }121             }122             xzb.pop();123             yzb.pop();124          }125         }126 }127 int main()128 {129     130     scanf("%d%d",&n,&m);131     int bgx=0;132     int bgy=0;133     for(int i=1;i<=n;i++)134     {135         for(int j=1;j<=m;j++)136         {137             char c;138             cin>>c;139             if(c==‘.‘)140             map[i][j]=0;141             else if(c==‘X‘)142             map[i][j]=1;// 不能走143             else if(c==‘*‘)144             {145                 //map[i][j]=3;146                 bgx=i;147                 bgy=j;148              } 149         }150     }151     152     scanf("%d",&p);153     for(int i=1;i<=p;i++)154     {155         string kk;156         cin>>kk;157         if(kk[0]==‘N‘)158         fx[i]=1;// 1上159         else if(kk[0]==‘S‘)160         fx[i]=2;// 2下161         else if(kk[0]==‘W‘)162         fx[i]=3;// 3左163         else fx[i]=4;//  4右 164     }165     xzb.push(bgx);166     yzb.push(bgy);167     bfs(bgx,bgy);168     for(int i=1;i<=n;i++)169     {170         for(int j=1;j<=m;j++)171         {172             if(map[i][j]==0)173             printf(".");174             else if(map[i][j]==1)175             printf("X");176             else 177             printf("*");178         }179         printf("\n");180     }181     return 0;182 }