简单版贪吃蛇 
Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte
Total Submit: 22 Accepted: 13 Special Judge
Total Submit: 22 Accepted: 13 Special Judge
Description
现在我们来简化蛇的身体，假设初始化的时候蛇的身体只有一个头而已（呵，当然是假设的），那么蛇去吃食物的时候就不必考虑碰到自己的身体了。
例：
5 5 ..... S.... ###.# E.... #####
那么从S到E最短的走法是EEESSWWW。说明：N（north），S（south），W（west），E（east）。如果吃不到食物就输出Can't eat it!
注意：路径是最短的走的。
Input
输入数据有多组，每组输入的第一行是两个正整数R，C，表示行和列，3=<R，C<=100，下面输入R行C列的矩阵。
输入保证合法。
Output
每行输出最短的走法。
Sample Input
5 5 ..... S.... ###.# E.... #####
Sample Output
EEESSWWW
Uploader
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> const int INF = 0x7fffffff; using namespace std; const int maxn = 110; char g[maxn][maxn]; int n, m; int used[maxn][maxn];//保存从s到这点最小步数 string trace[maxn][maxn];//记录路径. struct info { int x; int y; int time; }; info start, endx; queue<info> Q; void init() { while(!Q.empty()) Q.pop(); memset(g, '\0', sizeof(g)); } void bfs() { Q.push(start); info tmp, in; while(!Q.empty()) { tmp = Q.front(); Q.pop(); if(tmp.x - 1 >= 1 && g[tmp.x-1][tmp.y] != '#'){// up if(tmp.time + 1 < used[tmp.x-1][tmp.y]) { used[tmp.x-1][tmp.y] = tmp.time + 1; trace[tmp.x-1][tmp.y] = trace[tmp.x][tmp.y] + 'N'; in.x = tmp.x - 1; in.y = tmp.y; in.time = used[tmp.x-1][tmp.y]; Q.push(in); } } if(tmp.x + 1 <= n && g[tmp.x+1][tmp.y] != '#') {//down if(tmp.time + 1 < used[tmp.x+1][tmp.y]) { used[tmp.x+1][tmp.y] = tmp.time + 1; trace[tmp.x+1][tmp.y] = trace[tmp.x][tmp.y] + 'S'; in.x = tmp.x + 1; in.y = tmp.y; in.time = used[tmp.x+1][tmp.y]; Q.push(in); } } if(tmp.y - 1 >= 1 && g[tmp.x][tmp.y-1] != '#') {//left if(tmp.time + 1 < used[tmp.x][tmp.y-1]) { used[tmp.x][tmp.y-1] = tmp.time + 1; trace[tmp.x][tmp.y-1] = trace[tmp.x][tmp.y] + 'W'; in.x = tmp.x; in.y = tmp.y - 1; in.time = used[tmp.x][tmp.y-1]; Q.push(in); } } if(tmp.y + 1 <= m && g[tmp.x][tmp.y+1] != '#') {//right if(tmp.time + 1 < used[tmp.x][tmp.y+1] ) { used[tmp.x][tmp.y+1] = tmp.time + 1; trace[tmp.x][tmp.y+1] = trace[tmp.x][tmp.y] + 'E'; in.x = tmp.x; in.y = tmp.y + 1; in.time = used[tmp.x][tmp.y+1]; Q.push(in); } } } if(used[endx.x][endx.y] == INF) { printf("Can't eat it!\n"); } else { cout << trace[endx.x][endx.y] << endl; } } int main() { int i, j; while(scanf("%d%d", &n, &m) != EOF) { init(); for(i = 1; i <= n; i++) { scanf("%s", g[i]+1); } for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { if(g[i][j] == 'S') { start.x = i; start.y = j; start.time = 0; used[i][j] = 0;//开始步数. } if(g[i][j]=='E') { endx.x = i; endx.y = j; } if(g[i][j] != 'S') used[i][j] = INF;//初始化每个值. trace[i][j].clear(); } } bfs(); } return 0; }#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <queue> #include <algorithm> using namespace std; const int N = 105; //注释：这是宾哥的代码，感觉写的不错，以后A掉题目后也有借鉴别人的代码风格。 int n, m; char map[N][N]; struct Point { int x, y; string steps; }; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; // E, W, S, N string ds[] = {"E", "W", "S", "N"}; bool ok(int x, int y) { return (x >= 0 && x < m && y >= 0 && y < n && map[x][y] != '#'); } Point you; string bfs() { queue<Point> Q; Q.push(you); Point cur, nex; while(!Q.empty()) { cur = Q.front(); Q.pop(); for(int i = 0; i < 4; i++) { nex.x = cur.x + dx[i]; nex.y = cur.y + dy[i]; if(!ok(nex.x, nex.y)) continue; if(map[nex.x][nex.y] == 'E') { return cur.steps + ds[i]; } nex.steps = cur.steps + ds[i]; map[nex.x][nex.y] = '#'; Q.push(nex); } } return "-1"; } int main() { while(scanf("%d%d", &m, &n) != EOF) { for(int i = 0; i < m; i++) { scanf("%s", map[i]); for(int j = 0; j < n; j++) { if(map[i][j] == 'S') { you.x = i; you.y = j; map[i][j] = '#'; you.steps = ""; } } } string ans = bfs(); if(ans == "-1") printf("Can't eat it!"); else cout << ans; printf("\n"); } return 0; }