圖-BFS

poj題目：走出迷宮

描述

當你站在一個迷宮裡的時候，往往會被錯綜複雜的道路弄得失去方向感，如果你能得到迷宮地圖，事情就會變得非常簡單。

假設你已經得到了一個n*m的迷宮的圖紙，請你找出從起點到出口的最短路。

輸入

第一行是兩個整數n和m(1 <= n,m <= 100)，表示迷宮的行數和列數。

接下來n行，每行一個長為m的字元串，表示整個迷宮的布局。字元.表示空地，#表示牆，S表示起點,T表示出口。

輸出

輸出從起點到出口最少需要走的步數。(你不能起出迷宮外)

樣例輸入

3 3

S#T

.#.

...

樣例輸出

6

/*n1代表truen0代表false n*/ nint ex,ey,n,m; // ex, ey 終點坐標 n m 行 列 nint dx[4]={0,0,-1,1}; nint dy[4]={1,-1,0,0}; nstruct Node{ n int x,y; n int step; //走到當前點的步數 n}S; // S起點 nchar map[101][101]; // 迷宮輸入 nint vis[101][101]; // 是否已經走過 nqueue<Node> q; // 用於存放即將輻射的隊列 nint fun(int x,int y) //判斷這個點是否能走 n{ n if((x>=0&&x<n&&y>=0&&y<m)&&vis[x][y]==0&&map[x][y]!=#) return 1; n else return 0;n} nint bfs() n{ n q.push(S); n vis[S.x][S.y]=1; n while(!q.empty()) n { n Node top; n top=q.front(); n q.pop(); n if(top.x==ex&&top.y==ey) n { n return top.step; n } n for(int i=0;i<4;i++) n { n int xx=top.x+dx[i]; n int yy=top.y+dy[i]; n if(fun(xx,yy)==1 && vis[xx][yy]==0) // (xx, yy)是一個合法節點 n { n vis[xx][yy]=1; // 設置節點顏色 n Node node; n node.x=xx,node.y=yy,node.step=top.step+1; n q.push(node); n } n } n } n} n nint main() n{ n memset(vis,0,sizeof(vis)); n scanf("%d %d",&n,&m); n for(int i=0;i<n;i++) n scanf("%s",map[i]); n scanf("%d %d %d %d",&S.x,&S.y,&ex,&ey); n S.step=0; n printf("%d",bfs()); n return 0; n} n友情鏈接：http://blog.csdn.net/raphealguo/article/details/7523411n

推薦閱讀：