迷宮問題(DFS)
聲明：圖片及內容基於//www.bilibili.com/video/BV1oE41177wk?t=3245
問題及分析
8*8的迷宮，最外周是牆，0表示可以走，1表示不可以走
設置迷宮
const int M = 8; //迷宮長（不包含牆）
const int N = 8; //迷宮寬（不包含牆）
設置方位坐標
class Box{ //棧中元素
public:
int x, y;
int di; //方向及Direction數組的下標
Box(int x, int y, int di):x(x),y(y),di(di) {}
Box() {}
};
設置方位偏移量
class Direction{ //x,y方向增量
public:
int incX, incY;
Direction(int x, int y) :incX(x), incY(y) {}
};
尋找路徑
bool findPath(int maze[M + 2][N + 2], Direction direct[], stack<Box> &s) {
Box temp(1,1,-1); //temp用來記錄當前所在位置
int x, y, di; //迷宮格子當前處理單元的縱橫坐標和方向
int line, col; //迷宮數組下一個單元的行坐標和列坐標
maze[1][1] = -1; //走過的格子設為-1
s.push(temp);
while (!s.empty()) {
temp = s.top(); //每次獲取棧的頭元素
s.pop(); //彈出頭元素
x = temp.x; y = temp.y; di = temp.di+1; //上次循環到沒法走要換個方向，更新當前位置，下，x，y不變，di+1，換個方向
while (di < 4) {
line = x + direct[di].incX;
col = y + direct[di].incY;
if (maze[line][col] == 0) { //格子為0說明這個格子可以走
Box temp2(x, y, di);
temp = temp2;
s.push(temp); //成功走到下一個格子就壓入棧
x = line; y = col; maze[line][col] = -1; //更新當前所在位置
if (x == M && y == N) return true;
else di = 0; //從最新的位置開始嘗試四個方向
}
else di++; //maze[line][col]== -1 沒法走，換一個方向
}
}
return false; //沒有路
}
彈出元素就是回退，壓入元素就是前進。
內層循環對下一個位置的方向進行判斷，若符合要求則將目前位置坐標壓棧，並將處理坐標移到下一個位置。
外層循環則是當目前位置無法繼續前進，彈棧，回到上一位置，對其它方向進行嘗試。
完整程式碼
#include<iostream>
#include<stack>
using namespace std;
const int M = 8; //迷宮長（不包含牆）
const int N = 8; //迷宮寬（不包含牆）
class Direction{ //x,y方向增量
public:
int incX, incY;
Direction(int x, int y) :incX(x), incY(y) {}
};
class Box{ //棧中元素
public:
int x, y;
int di; //方向及Direction數組的下標
Box(int x, int y, int di):x(x),y(y),di(di) {}
Box() {}
};
bool findPath(int maze[M + 2][N + 2], Direction direct[], stack<Box> &s) {
Box temp(1,1,-1); //temp用來記錄當前所在位置
int x, y, di; //迷宮格子當前處理單元的縱橫坐標和方向
int line, col; //迷宮數組下一個單元的行坐標和列坐標
maze[1][1] = -1; //走過的格子設為-1
s.push(temp);
while (!s.empty()) {
temp = s.top(); //每次獲取棧的頭元素
s.pop(); //彈出頭元素
x = temp.x; y = temp.y; di = temp.di+1;
while (di < 4) {
line = x + direct[di].incX;
col = y + direct[di].incY;
if (maze[line][col] == 0) { //格子為0說明這個格子可以走
Box temp2(x, y, di);
temp = temp2;
s.push(temp); //成功走到下一個格子就壓入棧
x = line; y = col; maze[line][col] = -1;
if (x == M && y == N) return true;
else di = 0; //從最新的位置開始嘗試四個方向
}
else di++; //換一個方向
}
}
return false; //沒有路
}
int main() {
stack<Box> s;
Direction direct[4] = { {0,1},{1,0},{0,-1},{-1,0} };
int maze[M + 2][N + 2];
for (int i = 0; i < M + 2; i++) {
for (int j = 0; j < N + 2; j++) {
cin >> maze[i][j];
}
}
int maze2[M+2][N+2]; //用maze2拷貝maze用於最後列印
for (int i = 0; i < M + 2; i++) {
for (int j = 0; j < N + 2; j++) {
maze2[i][j]= maze[i][j];
}
}
if (findPath(maze, direct, s)) {
while (!s.empty()) {
cout << "(" << s.top().x << "," << s.top().y << ")" << endl;
maze2[s.top().x][s.top().y] = s.top().di + 2; //類似哈希散列，做特殊標記。牆是0~1，箭頭是2~5
s.pop(); //為了實現可視化
}
for (int i = 0; i < M + 2; i++) { //路徑可視化
for (int j = 0; j < N + 2; j++) {
switch (maze2[i][j]) {
case 0:cout << "0 "; break;
case 1:cout << "1 "; break;
case 2:cout << "→"; break;
case 3:cout << "↓"; break;
case 4:cout << "←"; break;
case 5:cout << "↑"; break;
default:break;
}
//cout << maze2[i][j]<<" ";
}
cout << endl;
}
}
else cout << "No path"<<endl;
return 0;
}
輸入：
1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1 0 1
1 0 0 0 0 1 1 0 0 1
1 0 1 1 1 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1
1 0 1 0 0 0 1 0 0 1
1 0 1 1 1 0 1 1 0 1
1 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
輸出：
(8,7)
(8,6)
(8,5)
(7,5)
(6,5)
(6,4)
(6,3)
(5,3)
(5,2)
(5,1)
(4,1)
(3,1)
(3,2)
(2,2)
(1,2)
(1,1)
1 1 1 1 1 1 1 1 1 1
1 →↓1 0 0 0 1 0 1
1 0 ↓1 0 0 0 1 0 1
1 ↓←0 0 1 1 0 0 1
1 ↓1 1 1 0 0 0 0 1
1 →→↓1 0 0 0 0 1
1 0 1 →→↓1 0 0 1
1 0 1 1 1 ↓1 1 0 1
1 1 0 0 0 →→→0 1
1 1 1 1 1 1 1 1 1 1
