3128: 简单版贪吃蛇  时间限制(普通/Java):1000MS/3000MS     内存限制:65536KByte 总提交: 545            测试通过:169 Special Judge 描述 现在我们来简化蛇的身体，假设初始化的时候蛇的身体只有一个头而已（呵，当然是假设的），那么蛇去吃食物的时候就不必考虑碰到自己的身体了。 例： 5 5 ..... S.... ###.# E.... #####
那么从S到E最短的走法是EEESSWWW。说明：N（north），S（south），W（west），E（east）。如果吃不到食物就输出Can't eat it! 注意：路径是最短的走的。 输入 输入数据有多组，每组输入的第一行是两个正整数R，C，表示行和列，3=<R，C<=100，下面输入R行C列的矩阵。 输入保证合法。 输出 每行输出最短的走法。 样例输入
5 5 ..... S.... ###.# E.... #####
样例输出
EEESSWWW
解题思路：
这个题目只是简单的广搜，只是多了一个记录最短路路径，方法是我定义了四个方向dir[4][2]（上N，右E，下S，左W）的方向定义的， 我先在用一个字符串string ch="NESW",与我所定义的搜索方向相对应，则我搜索dir[i][0]方向时，如果这个方向的这个位置符合条件， 我就在这个路径上加上对应的ch[i],就能记录路径的方向。用string类型很好实现
题目代码： #include<iostream> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #define max(a,b) a>b?a:b #define INF 0x3f3f3f3f using namespace std; char Map[103][103]; int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; //N,E,S,W，北，东，南，西 string ch="NESW";  //与搜索的四个方向顺序对应的四个方向 int vis[103][103]; //用于标记的数组 int R,C; //行，列 struct pos //位置 { int x; int y; string path;  //到达当前位置的最短路径 }; void bfs(int x1,int y1,int x2,int y2) //传入起点终点的坐标 { int i; pos cur,nex;  //当前位置，下一位置 memset(vis,0,sizeof(vis)); //vis初始化为0 vis[x1][y1]=1;  //起点标记，代表访问过了 cur.x=x1;  //起点横坐标为x1, cur.y=y1; //起点纵坐标为y1 cur.path="";  //路径初始化为空 queue<pos>Q; Q.push(cur); while(!Q.empty()) { cur=Q.front(); Q.pop(); if(cur.x==x2&&cur.y==y2) { cout<<cur.path<<endl; //如果当前位置是终点，我要输出当前位置的路径 return;     //结束广搜 } for(i=0;i<4;i++) { nex.x=cur.x+dir[i][0]; //搜索下一位置 nex.y=cur.y+dir[i][1]; if(nex.x>0&&nex.x<=R&&nex.y>0&&nex.y<=C&&Map[nex.x][nex.y]!='#'&&!vis[nex.x][nex.y]) //下一位置不越界，能行走，且没被访问过 { nex.path=cur.path+ch[i];  //下一位置的路径，等于当前位置的路径加上当前的转向 // cout<<nex.path<<endl; vis[nex.x][nex.y]=1;  //标记这个位置被访问过了 Q.push(nex);    //入队 } } } printf("Can't eat it!\n");  //吃不到，输出Can't eat it! return; } int main() { int i,j,sx,sy,ex,ey; while(~scanf("%d%d",&R,&C)) { for(i=1;i<=R;i++) for(j=1;j<=C;j++) { scanf(" %c",&Map[i][j]); if(Map[i][j]=='S') { sx=i; sy=j; } if(Map[i][j]=='E') { ex=i; ey=j; } } bfs(sx,sy,ex,ey); } return 0; }