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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-04-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录