（轉）POJ 2049 走迷宮選取經過門最少的路線 BFS搜尋

Finding Nemo

Time Limit: 2000MS	Memory Limit: 30000K
Total Submissions: 9778	Accepted: 2334

Description

Nemo is a naughty boy. One day he went into the deep sea all by himself. Unfortunately, he became lost and couldn't find his way home. Therefore, he sent a signal to his father, Marlin, to ask for help. 

After checking the map, Marlin found that the sea is like a labyrinth with walls and doors. All the walls are parallel to the X-axis or to the Y-axis. The thickness of the walls are assumed to be zero. 

All the doors are opened on the walls and have a length of 1. Marlin cannot go through a wall unless there is a door on the wall. Because going through a door is dangerous (there may be some virulent medusas near the doors), Marlin wants to go through as few doors as he could to find Nemo. 

Figure-1 shows an example of the labyrinth and the path Marlin went through to find Nemo. 

We assume Marlin's initial position is at (0, 0). Given the position of Nemo and the configuration of walls and doors, please write a program to calculate the minimum number of doors Marlin has to go through in order to reach Nemo.

Input

The input consists of several test cases. Each test case is started by two non-negative integers M and N. M represents the number of walls in the labyrinth and N represents the number of doors. 

Then follow M lines, each containing four integers that describe a wall in the following format: 

x y d t 

(x, y) indicates the lower-left point of the wall, d is the direction of the wall -- 0 means it's parallel to the X-axis and 1 means that it's parallel to the Y-axis, and t gives the length of the wall. 

The coordinates of two ends of any wall will be in the range of [1,199]. 

Then there are N lines that give the description of the doors: 

x y d 

x, y, d have the same meaning as the walls. As the doors have fixed length of 1, t is omitted. 

The last line of each case contains two positive float numbers: 

f1 f2 

(f1, f2) gives the position of Nemo. And it will not lie within any wall or door. 

A test case of M = -1 and N = -1 indicates the end of input, and should not be processed.

Output

For each test case, in a separate line, please output the minimum number of doors Marlin has to go through in order to rescue his son. If he can't reach Nemo, output -1.

Sample Input

8 9
1 1 1 3
2 1 1 3
3 1 1 3
4 1 1 3
1 1 0 3
1 2 0 3
1 3 0 3
1 4 0 3
2 1 1
2 2 1
2 3 1
3 1 1
3 2 1
3 3 1
1 2 0
3 3 0
4 3 1
1.5 1.5
4 0
1 1 0 1
1 1 1 1
2 1 1 1
1 2 0 1
1.5 1.7
-1 -1      

Sample Output

5
-1      

Source

Beijing 2004 解析連結： POJ 2049 走迷宮選取經過門最少的路線 BFS搜尋   寫的真的非常好！！！

很經典的BFS搜尋 走迷宮選取經過門最少的路線，這題POJ測試資料設計不全面，changeDir數組指派錯誤也可以過。。。

主要圖的資料結構存儲方式和算法實作參考了http://blog.csdn.NET/bobten2008/article/details/5093307

(1)首先是建圖, 由于輸入給的都是線段, 但是我們平常處理這類問題都是轉換為網格來做的, 是以需要将線段轉換為網格.轉化的方法是對于每個格子,用其左上角點的坐标來表示這個格子。如果其左上角點的坐标是[i][j],那麼這個格子就表示為[i][j].将其四周邊界的四條線段歸這個格子管.即為每個格子建一個數組round[i][j][4],第三維的四個位置分别表示這四條線段的類型(0-3分别對應上下左右): 數組元素的值0表示空氣,1表示牆,2表示是一扇門,這樣這個模型就建立好了.

(2)其次是bfs的起始點選為Nemo所在的位置,注意要将這個浮點點位置轉化為格子的坐标.轉化的方法很簡單.對于x坐标取整即可,對于y坐标取整+1即可,比如Nemo所在位置為[1.2, 1.3]那麼轉化為格子的坐标即為:[1, 2].這個坐标即位bfs周遊的起始點

(3)周遊的時候如果所走的方向是牆,則不可走.如果是門則将目前總的steps數+1,如果為空氣,steps數不變.另外一點就是如何判重.判重不能簡單地記錄有沒有被通路過,而是需要記錄到目前格子的最小步驟.如果目前總步驟數小于目前格子的最小步驟數,則更新其最小步驟數并将這個格子加入隊列中.

(4)周遊的終止位置即為題目中的出發位置[0, 0]

Source Code

Problem: 2049	User: yangliuACMer
Memory: 1160K	Time: 250MS
Language: C++	Result: Accepted

[cpp]  view plain  copy

1. #include <iostream>  
2. #include <queue>  
3. #define MAX_N 210   
4. using namespace std;  
5. int v[MAX_N + 1][MAX_N + 1]; //v[i][j]為到達格子[i][j]的最小步驟數  
6. int round[MAX_N + 1][MAX_N][4]; //用左上角點的坐标來指代格子，第三維0、1、2、3指定了該數組元素對應上、下、左、右邊，數組的值表明了該邊的類型 0空氣 1牆 2門  
7. int wn, dn, startXI, startYI, minSteps;//wn牆數量 dn門的數量 起點對應的格子坐标  
8. double startXF, startYF;//起點的輸入浮點坐标  
9. int dirarray[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};//方向數組，走四個方向時坐标的變換 分别為上、下、左、右  
10. //加入bfs隊列的元素類型  
11. struct elem{  
12.     //x、y為這個格子的坐标，dir記錄了是從目前格子的那個方向進入到這個格子的， 上0 下1 左2 右3  
13.     int x, y, dir, stepnum;//stepnum為到達目前格子所需要的步驟數量  
14. };  
15. queue<elem> bfsq;  
16. //取目前方向的對面方向  
17. void changeDir(int orginal, int &newDir){  
18.     if(orginal == 0) newDir = 1;  
19.     else if(orginal == 1) newDir = 0;//這裡下的反方向肯定是上，POJ測試用例不全面，這裡改成1也能AC  
20.     else if(orginal == 2) newDir = 3;  
21.     else newDir = 2;  
22. }  
23. //判斷目前坐标是否在合法範圍之内  
24. bool inRange(int x, int y){  
25.     return x >= 0 && x <= 205 && y >= 0 && y<= 205;  
26. }  
27. void bfs(){  
28.     //将Nemo的位置加入隊列作為bfs搜尋的起始位置  
29.     while(!bfsq.empty()) bfsq.pop();  
30.     elem curelem, newelem;  
31.     curelem.x = startXI; curelem.y = startYI; curelem.dir = -1; curelem.stepnum = 0;  
32.     v[startXI][startYI] = 0;  
33.     bfsq.push(curelem);  
34.     int curx, cury, curdir, cursteps, newx, newy, newdir, newsteps, d;  
35.     while(!bfsq.empty()){//實作圖的廣度周遊即層次式的周遊都要借助于隊列  
36.         curelem = bfsq.front();  
37.         bfsq.pop();  
38.         curx = curelem.x; cury = curelem.y; curdir = curelem.dir; cursteps = curelem.stepnum;  
39.         //到達原點  
40.         if(curx == 0 && cury == 0){  
41.             if(cursteps < minSteps)  
42.                 minSteps = cursteps;  
43.             continue;  
44.         }  
45.         //周遊目前格子的四個方向，嘗試向四個方向走  
46.         for(d = 0; d < 4; d++){  
47.             //不能向回走  
48.             if(d != curdir){  
49.                 //所走的方向不能是牆  
50.                 if(round[curx][cury][d] != 1){  
51.                     //得到新的格子的坐标  
52.                     newx = curx + dirarray[d][0];//要注意這種方向數組的用法，很巧妙！  
53.                     newy = cury + dirarray[d][1];  
54.                     //判定新坐标是否在合法的範圍内  
55.                     if(inRange(newx, newy)){  
56.                         //計算所有相對目标格子所在的方位  
57.                         changeDir(d, newdir);  
58.                         //如果是門，步驟數+1  
59.                         if(round[curx][cury][d] == 2)  
60.                             newsteps = cursteps + 1;  
61.                         else //如果是空氣步驟數目不變  
62.                             newsteps = cursteps;  
63.                         //判斷目前的新格子的新狀态是否需要加入隊列  
64.                         if(v[newx][newy] == 0xbf || newsteps < v[newx][newy] && newsteps < minSteps){  
65.                             v[newx][newy] = newsteps;  
66.                             newelem.x = newx; newelem.y = newy; newelem.stepnum = newsteps; newelem.dir = newdir;  
67.                             bfsq.push(newelem);  
68.                         }  
69.                     }  
70.                 }  
71.             }  
72.         }  
73.     }  
74. }  
75. int main(){  
76.     int i, j, x, y, d, t;  
77.     while(scanf("%d%d", &wn, &dn) && !(wn == -1 && dn == -1)){  
78.         minSteps = INT_MAX;  
79.         memset(v, 12, sizeof(v));  
80.         memset(round, 0, sizeof(round));  
81.         for(i = 1; i <= wn; i++){  
82.             cin>>x>>y>>d>>t;  
83.             //輸入預處理，把門和牆轉化為格子對應的四面邊界  
84.             if(d == 1)//與y軸平行  
85.                 for(j = y + 1; j <= y + t; j++)//數組的值為格子類型 0為空氣 1為牆 2為門  
86.                     round[x][j][2] = round[x - 1][j][3] = 1;//第三維為方向 0上 1下 2左 3右  
87.             else  
88.                 for(j = x; j < x + t; j++)  
89.                     round[j][y][0] = round[j][y + 1][1] = 1;  
90.         }  
91.         for(i = 1; i <= dn; i++){  
92.             cin>>x>>y>>d;  
93.             if(d == 1)  
94.                 round[x][y + 1][2] = round[x - 1][y + 1][3] = 2;  
95.             else   
96.                 round[x][y][0] = round[x][y + 1][1] = 2;  
97.         }  
98.         cin>>startXF>>startYF;//Nemo位置  
99.         startXI = startXF;  
100.         startYI = startYF +1;  
101.         //一場輸入處理  
102.         if(startXI < 0 || startXI > 199 || startYI < 0 ||startYI > 199)  
103.             cout<<0<<endl;  
104.         else{  
105.             bfs();  
106.             if(minSteps == INT_MAX) cout<<"-1"<<endl;  
107.             else cout<<minSteps<<endl;  
108.         }  
109.     }  
110.     return 0;  
111. }