逃跑的拉尔夫
题目描述 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(东)，表示汽车移动的方向，任何两个连续的方向都不相同。
输出文件应包含用R行表示的小镇的地图(象输入文件中一样)，字符“*”应该仅用来表示汽车最终可能出现的位置。
样例输入 Sample Input
4 5
.....
.X...
...*X
X.X..
3
NORTH
WEST
SOUTH
样例输出 Sample Output
.....
*X*..
*.*.X
X.X..
基本思想：利用广度优先算法：一个一个方向的遍历，每走一个方向，把该方向能够到达的节点入队列，计算过的节点出队，直到所有方向都遍历过一遍。
数据结构：队列，二维数组。
代码已经加上了注释，其中有测试用的函数：
#include<stdio.h>
#include<string.h>
void print();
int visit[100][100];
//void test();
int e[100][100],dir[1005];
int r,c,n;
struct node{
int x;
int y;
};
struct node que[1000000];
int head,tail;
int main()
{
int i,j,starx,stary,x,y,len1,len2=0;
char s[100];
scanf("%d %d",&r,&c);
for(i=1;i<=r;i++)//初始化二维数组
{
scanf("%s",s);
for(j=1;j<=c;j++)
{
if(s[j-1]=='.') e[i][j]=1;
else if(s[j-1]=='*')
{
e[i][j]=1;
stary=i;
starx=j;
}
else e[i][j]=0;
}
}
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%s",s);
if(s[0]=='N') dir[i]=0;
if(s[0]=='S') dir[i]=1;
if(s[0]=='W') dir[i]=2;
if(s[0]=='E') dir[i]=3;
}
head=tail=1;//初始化队列
que[1].x=starx;
que[1].y=stary;
tail++;
len1=1;
len2=0;
int dirction[4][2]={{0,-1},{0,1},{-1,0},{1,0}};//根据东西南北定方向
for(i=1;i<=n;i++)
{
memset(visit,0,sizeof(visit));
//test();
for(j=1;j<=len1;j++)//把该方向能够到达的节点都入队，注意利用visit判重
{
x=que[head].x;
y=que[head].y;
while(1)
{
x+=dirction[dir[i]][0];
y+=dirction[dir[i]][1];
// printf("%d %d %d %d\n",x,y,dirction[dir[i]][0],dirction[dir[i]][1]);
//getch();
if(x>=1&&x<=c&&y>=0&&y<=r&&e[y][x]==1&&visit[x][y]==0)//判断条件
{
que[tail].x=x;
que[tail].y=y;
visit[x][y]=1;
tail++;
len2++;
}
else
break;
}
head++;//处理过的节点出队
}
len1=len2;//入队的节点数，即需要处理的节点数
len2=0;
}
// test();
while(head<tail) //根据队列该成 *
{
e[que[head].y][que[head].x]=3;
head++;
}
print();//输出
return 0;
}
/*void test()
{
int i=head ,j=tail;
printf("\n************\n");
while(i<j)
{
printf("x=%d , y=%d\n",que[i].x,que[i].y);
i++;
}
printf("\n************\n");
}*/
void print()
{
int i,j;
for(i=1;i<=r;i++)
{
for(j=1;j<=c;j++)
{
if(e[i][j]==1) printf(".");
if(e[i][j]==3) printf("*");
if(e[i][j]==0) printf("X");
}
if(i!=r) printf("\n");
}
}
这里主要是利用的队列，，即出队，入队。
还有就是为什么要判重？ 为什么要用visit数组？
因为不判重que[]队列就会达到一个很大的数量级，比较浪费空间，所以通过判重来降低其数量级！
还有一种方法，，基本思想差不多，有可取之处：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char map[100][100];
char tu[100];
struct node
{
int x;int y;
}queue[1000000];
int head=0;
int tail=0;
bool visit[100][100];
char step[10];
int n,m;
int len;
int main()
{
scanf("%d%d",&n,&m);
memset(map,'X',sizeof(map));
for(int i=1;i<=n;i++)
{
scanf("%s",tu);
for(int j=1;j<=m;j++)
{
map[i][j]=tu[j-1];
if(map[i][j]=='*')
{
map[i][j]='.';
queue[++tail].x=i;
queue[tail].y=j;//把初始节点加入队列
}
}
}
scanf("%d",&len);
for(int i=1;i<=len;i++)
{
memset(visit,0,sizeof(visit));
scanf("%s",step);
int tail1=tail;
while(head<tail1)
{
node p=queue[++head];
visit[p.x][p.y]=false;//为什么？
if(step[0]=='N')
for(int j=1;map[p.x-j][p.y]!='X';j++)
{
if(!visit[p.x-j][p.y])
{
visit[p.x-j][p.y]=true;
queue[++tail].x=p.x-j;
queue[tail].y=p.y;
}
}
else if(step[0]=='S')
for(int j=1;map[p.x+j][p.y]!='X';j++)
{
if(!visit[p.x+j][p.y])
{
visit[p.x+j][p.y]=true;
queue[++tail].x=p.x+j;
queue[tail].y=p.y;
}
}
else if(step[0]=='W')
for(int j=1;map[p.x][p.y-j]!='X';j++)
{
if(!visit[p.x][p.y-j])
{
visit[p.x][p.y-j]=true;
queue[++tail].x=p.x;
queue[tail].y=p.y-j;
}
}
else if(step[0]=='E')
for(int j=1;map[p.x][p.y+j]!='X';j++)
{
if(!visit[p.x][p.y+j])
{
visit[p.x][p.y+j]=true;
queue[++tail].x=p.x;
queue[tail].y=p.y+j;
}
}
}
}
for(int i=head+1;i<=tail;i++)
map[queue[i].x][queue[i].y]='*';
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
printf("%c",map[i][j]);
printf("\n");
}
}