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; }
