noj->電子老鼠走迷宮
00 問題
有一隻電子老鼠被困在如下圖所示的迷宮中。這是一個12*12單元的正方形迷宮，黑色部分表示建築物，白色部分是路。電子老鼠可以在路上向上、下、左、右行走，每一步走一個格子。現給定一個起點S和一個終點T，求出電子老鼠最少要幾步從起點走到終點。 
輸入：
本題包含一個測例。在測例的第一行有四個由空格分隔的整數，分別表示起點的坐標S（x.y）和終點的坐標T（x,y）。從第二行開始的12行中，每行有12個字元，描述迷宮的情況，其中'X'表示建築物，'.'表示路.
輸出：
輸出一個整數，即電子老鼠走出迷宮至少需要的步數。
輸入樣例：
2 9 11 8
XXXXXXXXXXXX
X......X.XXX
X.X.XX.....X
X.X.XX.XXX.X
X.X.....X..X
X.XXXXXXXXXX
X...X.X....X
X.XXX...XXXX
X.....X....X
XXX.XXXX.X.X
XXXXXXX..XXX
XXXXXXXXXXXX
輸出樣例：
28
01 思路
01-1 類型
很明顯的一個迷宮了，並且要求出電子老鼠最少要幾步從起點走到終點，所以是廣搜類型。
01-2 演算法
-
第一步：設置入口出口和迷宮本體->init()函數
-
第二步：bfs主控函數：
-
隊列入出循環
-
生成四個節點 對四個節點進行判斷
-
如果新坐標為終點坐標，就返迴路徑長度
-
其他點：如果不是終點坐標，在迷宮內，未訪問過，不是牆，就入隊
-
入隊操作：
x.push(nextx);
y.push(nexty);
used[nextx][nexty]=1;
step[nextx][nexty]=step[prex][prey]+1; -
完成入隊出隊閉環。
-
-
-
輸出
-
02 程式碼
1 //電子老鼠闖迷宮 2 #include<iostream> 3 #include<queue> 4 5 using namespace std; 6 7 int map[13][13];//迷宮本體 8 int used[13][13]={0};//走過標記，0為未走，1為已走 9 int step[13][13]={0};//到達當前節點所走的步數 10 int inx,iny,outx,outy,prex,prey,nextx,nexty; 11 //分別是入口，出口，老位置、新位置 12 int dx[4] = {-1,1,0,0};//左右上下 13 int dy[4] = {0,0,-1,1};//左右上下 14 15 void init(); 16 int bfs(); 17 queue<int>x; 18 queue<int>y; 19 20 int main(){ 21 init();//初始化矩陣以及隊列 22 cout<<bfs()<<endl; 23 return 0; 24 } 25 void init(){ 26 int i,j; 27 char temp; 28 cin >> inx >> iny >> outx >> outy; 29 //初始化這個矩陣，方便起見，從1開始 30 for(i=1;i<13;i++){ 31 for(j=1;j<13;j++){ 32 cin>>temp; 33 if(temp == 'X'){ 34 map[i][j]=1; 35 } 36 else{ 37 map[i][j]=0; 38 } 39 } 40 } 41 //起點入隊 42 x.push(inx); 43 y.push(iny); 44 used[inx][iny]=1; 45 } 46 int bfs(){// 47 int i; 48 while(!x.empty()&&!y.empty()){ 49 prex = x.front(); 50 prey = y.front(); 51 x.pop(); 52 y.pop(); 53 //生成當前節點的四個子節點 54 for(i=0;i<4;i++){ 55 nextx = prex + dx[i]; 56 nexty = prey + dy[i]; 57 if(nextx==outx&&nexty==outy){ 58 //如果新坐標為終點坐標 59 return(step[prex][prey]+1); 60 } 61 if(nextx>0&&nextx<=12&&nexty>0&&nexty<=12&&used[nextx][nexty]==0&&map[nextx][nexty]==0){ 62 x.push(nextx); 63 y.push(nexty); 64 used[nextx][nexty]=1; 65 step[nextx][nexty]=step[prex][prey]+1; 66 } 67 } 68 } 69 return 0; 70 }
