# 深度优先搜索之栈解迷宫（C++）

## 程序范例

```/**
* 栈解迷宫 - 深度优先搜索.
*
*/
#include <iostream>
#include <stack>

#define LEFT 1
#define RIGHT 2
#define UP 3
#define DOWN 4

using namespace std;

struct Path {
int x;
int y;
};

int main() {
int m, n;
int maze[50][50];
int step[50][50];       // 标记有没有走过
int direct_mark[50][50][4];  // 标记某个点上的上下左右有没有走过
Path path;
path.x = 0;
path.y = 0;
stack<Path> path_stack; // 存放走的路径
std::cin>>m>>n;
if (m > 50 || n > 50) {
std::cout<<"the m or n is more than 50"<<std::endl;
return -1;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
std::cin>>maze[i][j];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
std::cout<<maze[i][j]<<' ';
}
std::cout<<std::endl;
}
std::cout<<std::endl;

path_stack.push(path);
step[path.x][path.y] = 1;
while (path_stack.size()) {
Path cur_path = path_stack.top();
int direct = 0;
if (cur_path.x == 3 && cur_path.y == 2) {
std::cout<<"find the point(49, 49), the step(s) is:"<<path_stack.size() - 1;
}
if (cur_path.x - 1 >= 0 && step[cur_path.x - 1][cur_path.y] == 0
&& maze[cur_path.x - 1][cur_path.y] == 0
&& direct_mark[cur_path.x][cur_path.y][LEFT - 1] == 0) {
direct = LEFT;
direct_mark[cur_path.x][cur_path.y][direct - 1] = 1;
} else if (cur_path.x + 1 <= 49 && step[cur_path.x + 1][cur_path.y] == 0
&& maze[cur_path.x + 1][cur_path.y] == 0
&& direct_mark[cur_path.x][cur_path.y][RIGHT - 1] == 0) {
direct = RIGHT;
direct_mark[cur_path.x][cur_path.y][direct - 1] = 1;
} else if (cur_path.y - 1 >= 0 && step[cur_path.x][cur_path.y - 1] == 0
&& maze[cur_path.x][cur_path.y - 1] == 0
&& direct_mark[cur_path.x][cur_path.y][UP - 1] == 0) {
direct = UP;
direct_mark[cur_path.x][cur_path.y][direct - 1] = 1;
} else if (cur_path.y + 1 <= 49 && step[cur_path.x][cur_path.y + 1] == 0
&& maze[cur_path.x][cur_path.y + 1] == 0
&& direct_mark[cur_path.x][cur_path.y][DOWN - 1] == 0) {
direct = DOWN;
direct_mark[cur_path.x][cur_path.y][direct - 1] = 1;
}
if (direct) {
switch (direct) {
case LEFT:
cur_path.x = cur_path.x - 1;
break;
case RIGHT:
cur_path.x = cur_path.x + 1;
break;
case UP:
cur_path.y = cur_path.y - 1;
break;
case DOWN:
cur_path.y = cur_path.y + 1;
break;
default:
break;
}
step[cur_path.x][cur_path.y] = 1;
path_stack.push(cur_path);
} else {
step[cur_path.x][cur_path.y] = 0;
path_stack.pop();
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
std::cout<<step[i][j]<<' ';
}
std::cout<<std::endl;
}
std::cout<<std::endl;
}
return 0;
}
```

o(m*n)