怎样将迷宫求解的栈替换成队列?

发布网友发布时间：2022-04-26 10:13

共1个回答

热心网友时间：2022-06-27 05:48

队列的先进先出实现了广度优先搜索。并且，在这个问题中，广度优先搜索和前两种方法相比的优势在于：
一，如果迷宫问题的解不止一个，那么广度优先搜索一定能够找到最短路径的解。因为，广度优先搜索的先进先出的特点，说明，它必定是先考虑了和目标点距离为1的所有候选点能否构成到达目标点的通路之后，再考虑和目标点距离为2的所有候选点能否构成到达目标点的通路，再考虑和目标点距离为3的所有点能否构成到达目标点的通路，以此类推，直到走到目标点位置。
二，广度优先搜索使用了队列，队列的head和tail指向的空间被放置了数据之后，就不会继续放数据了，所以这个空间的使用次数只有一次。这个和第一种方法中的栈不同，栈的top不停地push和pop，所以top所在的空间的使用次数可以为多次。队列的空间使用效率低于栈，这个trade-off的好处是，栈中用来记录探索通路的历史路径信息的predecessor数组的空间可以省下来。具体代码如下：

//队列版迷宫问题
struct point{int row, col,predecessor;} queue[512];
int head = 0, tail = 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 enqueue(struct point p)
{
queue[tail++] = p;
return;
}

struct point dequeque()
{
return queue[head++];
}

int is_empty()
{
return head == tail;
}

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');
}
printf("**********\n");
}

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

int main()
{
struct point p = {0,0,-1};
int MAX_ROW = 5;
int MAX_COL = 5;
maze[p.row][p.col] = 2;
enqueue(p);
while(!is_empty()) {
p = dequeque();
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);
if(p.row+1< MAX_ROW && maze[p.row+1][p.col] == 0)
visit(p.row+1,p.col);
if(p.col-1>=0 && maze[p.row][p.col-1] == 0)
visit(p.row,p.col-1);
if(p.row-1>=0 && maze[p.row-1][p.col] == 0)
visit(p.row-1,p.col);
// print_maze();
}
if(p.row == MAX_ROW -1 && p.col == MAX_COL -1) {
printf("(%d,%d)\n",p.row,p.col);
while(p.predecessor!= -1) {
p = queue[p.predecessor];
printf("(%d,%d)\n",p.row,p.col);
}
} else {
printf("No Path\n");
}
return 0;
}