十二、迷宫问题
十二、迷宮問題
文章目錄
- 十二、迷宮問題
- 題目描述
- 解題思路
- 上機代碼
題目描述
迷宮有一個入口，一個出口。一個人從入口走進迷宮，目標是找到出口。陰影部分和迷宮的外框為墻，每一步走一格，每格有四個可走的方向，探索順序為地圖方向：南（下）、東（右）、北（上）、西（左）。
-
輸入：輸入迷宮數組。第一行數據表示一個 n*n (n<=100)的迷宮；第二行開始的n行為迷宮數據。 其中：0表示路，1表示墻，起點在左上角 <1,1> 的位置，終點在右下角 <n,n> 的位置。
-
輸出：若有解，輸出從入口到出口的一條路徑，否則輸出 there is no solution!
例（上圖所示的迷宮數組）
輸入：
4 4
0 0 1 0
0 1 0 1
0 0 0 0
0 1 0 0
輸出：<1,1> <2,1> <3,1> <3,2> <3,3> <4,3> <4,4>
| 測試用例 1 | 4 4 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 | <1,1> <2,1> <3,1> <3,2> <3,3> <4,3> <4,4> | 1秒 | 64M | 0 |
| 測試用例 2 | 4 4 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 1 | There is no solution! | 1秒 | 64M | 0 |
| 測試用例 3 | 8 8 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 | <1,1> <1,2> <2,2> <3,2> <3,1> <4,1> <5,1> <5,2> <5,3> <6,3> <6,4> <6,5> <7,5> <8,5> <8,6> <8,7> <8,8> | 1秒 | 64M | 0 |
解題思路
迷宮問題是大家學習深度優先搜索（DFS）和廣度優先搜索（BFS）的經典問題之一，相信大家在參加集訓的時候肯定都學習過了，也都有對應的模板進行解答。針對此題，稍微改改代碼即可找到通過迷宮的路徑。
一般的迷宮問題都是求最終的路徑長度，而此題需要輸出具體走過的路徑。因此我們設置一個輔助結構 Position 來進行路徑的存儲，最后輸出 vector<Position> 中存儲的具體路徑即可。
考慮一種極端情況是，當終點是 1 的時候，是沒有任何一條的路徑可以通向終點的，這種情況直接輸出 There is no solution!，但是測試用例里似乎沒有出現這種情況，因此下面的代碼把它注釋了。
上機代碼
#include <iostream> #include <cstdio> #include <vector> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std;int map[110][110]; //模擬迷宮 int visit[110][110];//visit標記該位置是否走過 int n = 0, m = 0; int dx[4] = { 0,1,0,-1 }; int dy[4] = { -1,0,1,0 }; int sum = -9999; int num = 1; //設置一個輔助結構存儲對應路徑 struct Position {int x;int y; }; vector<Position>road; int dfs(int x, int y) {sum = max(sum, num);Position tmp;tmp.x = x;tmp.y = y;road.push_back(tmp);visit[x][y] = 1;if (x == n && y == m){sum = min(sum, num);return 1;}for (int i = 0; i<4; i++){int tx = x + dx[i];int ty = y + dy[i];if (!visit[tx][ty] && !map[tx][ty] && tx >= 1 && tx <= m && ty >= 1 && ty <= n){ //符合條件則繼續搜索num++;if (dfs(tx, ty))return 1;road.pop_back(); //返回原狀態visit[tx][ty] = 0; //返回原狀態num--;}}return 0; } int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){scanf("%d", &map[i][j]);}}// if (map[n][m] == 1)// {// printf("There is no solution!\n");// return 0;// }dfs(1, 1);if (sum<n + m - 1) { //沒有墻的話，迷宮走到終點的最少步數是n+m-1printf("There is no solution!\n");return 0;}else{for (int i = 0; i < road.size(); i++){printf("<%d,%d> ", road[i].x, road[i].y);}printf("\n");}return 0; }總結
