1026 逃跑的拉尔夫

淡淡的烟草味﹌ 2022-03-30 11:45 162阅读 0赞

### **1026 逃跑的拉尔夫**  ###

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

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

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

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

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

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

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

输入描述 Input Description

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

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

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

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

输出描述 Output Description

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

样例输入 Sample Input

4 5

.....

.X...

...\*X

X.X..

NORTH

WEST

SOUTH

样例输出 Sample Output

.....

\*X\*..

\*.\*.X

X.X..

数据范围及提示 Data Size & Hint

#### 分类标签  Tags [ 点此展开 ][Link 1]  ####

好吧我承认这道题我想复杂了。。。

无奈bfs水平实在太弱没写出来

只能用dfs

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     }

错误的bfs

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                  else
    116                  {
    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 }

[Link 1]: http://codevs.cn/problem/1026/#tags