1026 逃跑的拉尔夫

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..

3

NORTH

WEST

SOUTH

样例输出 Sample Output

.....

*X*..

*.*.X

X.X..

数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开

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

无奈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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

HYSBZ 2160 拉拉队排练(回文树)

2160: 拉拉队排练 Time Limit: 10 Sec  Memory Limit: 259 MB Submit: 825  Solved: 324 [...

3447
来自专栏F_Alex

数据结构与算法(一)-初识

前言:一个程序员前期可能需要各种业务和编程的能力,但是后期如果想要提高就需要有一个扎实的基础,厚积薄发,所以最近抽空学了下数据结构与算法,颇有感触,学习过程虽然...

1172
来自专栏数据结构与算法

P1996 约瑟夫问题

题目背景 约瑟夫是一个无聊的人!!! 题目描述 n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出...

3227
来自专栏喔家ArchiSelf

IOT语义互操作性之本体论

这个系列文章描述了一个单一的语义数据模型来支持物联网和建筑、企业和消费者的数据转换。 这种模型必须简单可扩展, 以便能够在各行业领域之间实现插件化和互操作性。 ...

1165
来自专栏take time, save time

你所能用到的数据结构(三)

三、对于效率提高的初次尝试     对于最自然的几种排序算法,数学家们开始思考如何提高排序算法的效率,可以通过数学证明出来如果想达到这个目的,必须想办法将相距...

2897
来自专栏我的python

递归方法的理解

递归思想算是编程中比较常见但对初学者而言又有些难以理解的方法了。在leetcode上刷了几道题都用递归思想成功解决后觉得应该贯彻互联网的开源共享精神,总结一下自...

1160
来自专栏懒人开发

(6.4)James Stewart Calculus 5th Edition:Work

牛顿第二定律: F = ma (这里 dv = ds/dt, da=dv/dt) 于是有

1072
来自专栏ACM算法日常

LIS的简单应用:UVA-437

上一次紫芝详细地介绍了动态规划中的经典问题LIS,今天我们抽出一个类似思想的简单题目进行实践练习。

1053
来自专栏机器学习算法与Python学习

长文 | 手把手教你如何使用python进行数据分析(最好将文章代码自己码一遍)

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 原文 http://www.cnbl...

3895
来自专栏张俊红

Python面向对象编程

2285

扫码关注云+社区

领取腾讯云代金券