问题

 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0

搜索过程

```2 1 0 0 0
2 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
**********
2 1 0 0 0
2 1 0 1 0
2 0 0 0 0
0 1 1 1 0
0 0 0 1 0
**********
2 1 0 0 0
2 1 0 1 0
2 2 0 0 0
2 1 1 1 0
0 0 0 1 0
**********
2 1 0 0 0
2 1 0 1 0
2 2 0 0 0
2 1 1 1 0
2 0 0 1 0
**********
2 1 0 0 0
2 1 0 1 0
2 2 2 0 0
2 1 1 1 0
2 0 0 1 0
**********
2 1 0 0 0
2 1 0 1 0
2 2 2 0 0
2 1 1 1 0
2 2 0 1 0
**********
2 1 0 0 0
2 1 2 1 0
2 2 2 2 0
2 1 1 1 0
2 2 0 1 0
**********
2 1 0 0 0
2 1 2 1 0
2 2 2 2 0
2 1 1 1 0
2 2 2 1 0
**********
2 1 2 0 0
2 1 2 1 0
2 2 2 2 0
2 1 1 1 0
2 2 2 1 0
**********
2 1 2 0 0
2 1 2 1 0
2 2 2 2 2
2 1 1 1 0
2 2 2 1 0
**********
2 1 2 0 0
2 1 2 1 0
2 2 2 2 2
2 1 1 1 0
2 2 2 1 0
**********
2 1 2 2 0
2 1 2 1 0
2 2 2 2 2
2 1 1 1 0
2 2 2 1 0
**********
2 1 2 2 0
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 0
**********
2 1 2 2 2
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 0
**********
2 1 2 2 2
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 2
**********
2 1 2 2 2
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 2
**********
2 1 2 2 2
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 2
**********
```

范例程式码（C++）

[code lang=”cpp”]
/**
* 队解迷宫算法.
*
* 利用广度优先算法.
*/
#include <iostream>
#include <cstdlib>

using namespace std;

#define MAX_ROW 5
#define MAX_COL 5

int tail = 0;

struct point {
int row;
int col;
int predecessor;
} queue[512];

int maze[MAX_ROW][MAX_COL] = {
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};

void enqueue(struct point p)
{
queue[tail++] = p;
return;
}

struct point dequeue()
{
struct point p;
return p;
}

int _is_empty()
{
}

void print_maze()
{
int i, j;
for (i = 0; i < MAX_ROW; i++) {
for (j = 0; j < MAX_COL; j++) {
cout<<maze[i][j]<<‘ ‘;
}
cout<<endl;
}
cout<<"**********"<<endl;
}

void visit(int row, int col)
{
struct point p = {row, col, head -1};
maze[row][col] = 2;
enqueue(p);
return;
}

int main(int argc, char * argv[])
{
struct point p;
visit(0, 0);
while (!_is_empty()) {
p = dequeue();
if (p.row == MAX_ROW – 1 && p.col == MAX_COL – 1)
{
break;
}
if( p.row + 1 < MAX_ROW && maze[p.row + 1][p.col] == 0)
{
visit(p.row + 1, p.col);
}
if( p.row – 1 >= 0 && maze[p.row – 1][p.col] == 0)
{
visit(p.row – 1, p.col);
}
if( p.col + 1 < MAX_COL && maze[p.row][p.col + 1] == 0)
{
visit(p.row, p.col + 1);
}
if( p.col – 1 >= 0 && maze[p.row][p.col – 1] == 0)
{
visit(p.row, p.col – 1);
}
print_maze();
}

if (p.row == MAX_ROW – 1 && p.col == MAX_COL – 1) {
cout<<‘(‘<<MAX_ROW – 1<<‘,'<<MAX_COL – 1<<‘)'<<endl;
while (p.predecessor != -1) {
p = queue[p.predecessor];
cout<<‘(‘<<p.row<<‘,'<<p.col<<‘)'<<endl;
}
} else {
cout<<"NO PATH"<<endl;
}
return 0;
}

[/code]

解法延伸

第一种，使用堆栈进行深度优先搜索。

[code lang=”cpp” collapse=”true”]
//堆栈版迷宫问题
struct point{int row, col;} stack[512];
int top = 0;
int LEN=5;
int maze[5][5] = {
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};
void push(struct point p)
{
stack[top++] = p;
return;
}
struct point pop()
{
return stack[–top];
}
int is_empty()
{
}
void print_maze()
{
int i,j;
for(i=0;i<LEN;i++)
{
for(j=0;j<LEN;j++)
printf("%d",maze[i][j]);
putchar(‘\n’);
}
printf("**********\n");
}
struct point predecessor[5][5] = {
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
};
void visit (int row, int col, struct point pre)
{
struct point visit_point = {row, col};
maze[row][col] = 2;
predecessor[row][col] = pre;
push(visit_point);
}
int main()
{
struct point p = {0,0};
int MAX_ROW = 5;
int MAX_COL = 5;
maze[p.row][p.col] = 2;
push(p);
while(!is_empty()) {
p = pop();
if(p.row == MAX_ROW -1 && p.col == MAX_COL -1)
break;
if(p.col+1< MAX_COL && maze[p.row][p.col+1] == 0)
visit(p.row,p.col+1,p);
if(p.row+1< MAX_ROW && maze[p.row+1][p.col] == 0)
visit(p.row+1,p.col,p);
if(p.col-1>=0 && maze[p.row][p.col-1] == 0)
visit(p.row,p.col-1,p);
if(p.row-1>=0 && maze[p.row-1][p.col] == 0)
visit(p.row-1,p.col,p);
print_maze();
}
if(p.row == MAX_ROW -1 && p.col == MAX_COL -1) {
printf("(%d,%d)\n",p.row,p.col);
while(predecessor[p.row][p.col].row != -1) {
p = predecessor[p.row][p.col];
printf("(%d,%d)\n",p.row,p.col);
}
} else {
printf("No Path\n");
}
return 0;
}
[/code]

第二种，使用递归(系统帮你进行了深度优先搜索)

[code lang=”cpp” collapse=”true”]
//递归版迷宫问题
struct point{int row, col;} stack[512];
int top = 0;
int MAX_ROW=5, MAX_COL=5;
int maze[5][5] = {
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};
void push(struct point p)
{
stack[top++] = p;
return;
}
struct point pop()
{
return stack[–top];
}
int is_empty()
{
}
void print_maze()
{
int i,j;
for(i=0;i<MAX_ROW;i++)
{
for(j=0;j<MAX_COL;j++)
printf("%d",maze[i][j]);
putchar(‘\n’);
}
}
struct point predecessor[5][5] = {
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
};
void visit (int row, int col, struct point pre)
{
maze[row][col] = 2;
predecessor[row][col] = pre;
}
void tranverse_maze(struct point& p)
{
std::cout<<"———"<<std::endl;
print_maze();
std::cout<<"———"<<std::endl;
std::cout<<p.row<<","<<p.col<<std::endl;
if(p.row == MAX_ROW -1 && p.col == MAX_COL -1)
{
return;
} else if (p.row+1<=MAX_ROW -1 && maze[p.row+1][p.col] == 0) {
visit(p.row+1,p.col,p);
p.row++;
tranverse_maze(p);
} else if (p.col-1>=0 && maze[p.row][p.col-1] == 0) {
visit(p.row,p.col-1,p);
p.col–;
tranverse_maze(p);
} else if (p.row-1>=0 && maze[p.row-1][p.col] == 0) {
visit(p.row-1,p.col,p);
p.row–;
tranverse_maze(p);
} else if (p.col+1<=MAX_COL-1 && maze[p.row][p.col+1] == 0) {
visit(p.row,p.col+1,p);
p.col++;
tranverse_maze(p);
} else {
p.row=predecessor[p.row][p.col].row;
p.col=predecessor[p.row][p.col].col;
tranverse_maze(p);
return;
}
}
int main()
{
print_maze();
struct point p = {0,0};
int MAX_ROW = 5;
int MAX_COL = 5;
maze[p.row][p.col] = 2;
tranverse_maze(p);
if(p.row == MAX_ROW -1 && p.col == MAX_COL -1) {
printf("(%d,%d)\n",p.row,p.col);
while(predecessor[p.row][p.col].row != -1) {
p = predecessor[p.row][p.col];
printf("(%d,%d)\n",p.row,p.col);
}
} else {
printf("No Path\n");
std::cout<<"———"<<std::endl;
std::cout<<p.row<<","<<p.col<<std::endl;
}
return 0;
}
[/code]

Share:

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