首页 > 代码库 > P1189 SEARCH
P1189 SEARCH
P1189 SEARCH
题目描述
年轻的拉尔夫开玩笑地从一个小镇上偷走了一辆车，但他没想到的是那辆车属于警察局，并且车上装有用于发射车子移动路线的装置。
那个装置太旧了，以至于只能发射关于那辆车的移动路线的方向信息。
编写程序，通过使用一张小镇的地图帮助警察局找到那辆车。程序必须能表示出该车最终所有可能的位置。
小镇的地图是矩形的，上面的符号用来标明哪儿可以行车哪儿不行。“.”表示小镇上那块地方是可以行车的，而符号“X”表示此处不能行车。拉尔夫所开小车的初始位置用字符的“*”表示，且汽车能从初始位置通过。
汽车能向四个方向移动：向北(向上)，向南(向下)，向西(向左)，向东(向右)。
拉尔夫所开小车的行动路线是通过一组给定的方向来描述的。在每个给定的方向，拉尔夫驾驶小车通过小镇上一个或更多的可行车地点。
输入输出格式
输入格式：
输入文件的第一行包含两个用空格隔开的自然数R和C，1≤R≤50，1≤C≤50，分别表示小镇地图中的行数和列数。
以下的R行中每行都包含一组C个符号(“.”或“X”或“*”)用来描述地图上相应的部位。
接下来的第R+2行包含一个自然数N，1≤N≤1000，表示一组方向的长度。
接下来的N行幅行包含下述单词中的任一个：NORTH(北)、SOUTH(南)、WEST(西)和EAST(东)，表示汽车移动的方向，任何两个连续的方向都不相同。
输出格式：
输出文件应包含用R行表示的小镇的地图(象输入文件中一样)，字符“*”应该仅用来表示汽车最终可能出现的位置。
输入输出样例
输入样例#1：
4 5......X......*XX.X..3NORTHWESTSOUTH
输出样例#1：
.....*X*..*.*.XX.X..
数组开大。（tur数组开成MAXN一直不过，orz！！！）
1 #include<cstdio> 2 #include<queue> 3 #include<iostream> 4 using namespace std; 5 6 const int MAXN = 52; 7 struct node{ 8 int x,y,step; 9 }cur,nxt;10 int tur[1010];11 int dx[5] = {0,1,0,-1}; //东南西北 12 int dy[5] = {1,0,-1,0};13 char mp[MAXN][MAXN],ch[10];14 bool v[MAXN][MAXN][1010];15 queue<node>q;16 int n,m,r;17 18 void bfs()19 {20 while (!q.empty())21 {22 cur = q.front();23 q.pop();24 if (cur.step==r)25 {26 mp[cur.x][cur.y] = ‘*‘;27 continue;28 }29 int ox = dx[tur[cur.step]], oy = dy[tur[cur.step]];30 int xx = cur.x+ox, yy = cur.y+oy;31 while (xx<=n&&yy<=m&&xx>0&&yy>0&&!v[xx][yy][cur.step+1]&&mp[xx][yy]!=‘X‘)32 {33 v[xx][yy][cur.step+1] = true;34 nxt.x = xx;35 nxt.y = yy;36 nxt.step = cur.step+1;37 q.push(nxt);38 xx += ox;39 yy += oy;40 }41 }42 }43 44 int main()45 {46 scanf("%d%d",&n,&m);47 for (int i=1; i<=n; ++i)48 for (int j=1; j<=m; ++j)49 {50 cin>>mp[i][j];51 if (mp[i][j]==‘*‘)52 {53 mp[i][j] = ‘.‘;54 cur.x = i;55 cur.y = j;56 cur.step = 0;57 q.push(cur);58 v[i][j][0] = true;59 }60 }61 scanf("%d",&r);62 for (int i=0; i<r; ++i) 63 {64 scanf("%s",ch);65 if (ch[0]==‘E‘) tur[i] = 0;66 else if (ch[0]==‘S‘) tur[i] = 1;67 else if (ch[0]==‘W‘) tur[i] = 2;68 else if (ch[0]==‘N‘) tur[i] = 3;69 }70 bfs();71 for (int i=1; i<=n; ++i)72 {73 for (int j=1; j<=m; ++j)74 printf("%c",mp[i][j]);75 printf("\n");76 }77 return 0;78 }
P1189 SEARCH
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。