在之前的一篇关于搜索的文章中《广度优先搜索算法队解迷宫问题》有提到深度优先搜索(dfs)算法,其中有一种就是本篇文章提到的实现方法:利用栈解迷宫;

广度优先搜索算法队解迷宫问题》中利用栈解迷宫有一个bug,比如:在x点出发,向右走直到尽头回到x点,此时在向其他方向(比如上),那么不能再走曾经向右走过的路(坐标)。

这次,我们增加一个direct_mark数组,来标记在每一个坐标上曾经走过的方向。

程序范例

[code lang=”cpp”]
/**
* 栈解迷宫 – 深度优先搜索.
*
* @authur genialx <admin@ihuxu.com>
*/
#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;
}
[/code]

时间复杂度

在一个m*n的迷宫中,最糟糕的情况是每个点的四个方向均探索了,即
o(m*n)


文章来源:胡旭博客 => 深度优先搜索之栈解迷宫(C++)

转载请注明出处,违者必究!

Share:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.