Question

关于广度优先搜索

迷宫问题：在一个迷宫中找出从入口到出口的一条步数最少的通路。看好题目是（最少的通路）！！！

Answer 1

恩，这个就是搜索树，进行广度优先遍历呀，也就是BFS算法，它可以保证结果是最优的，呵呵~~而深度优先搜索DFS是不能保证的哦……BFS算法也很好写的，用队列来维护即可~~下面给你一个参考题目和我的程序吧： http://poj.org/problem?id=3984 #include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int maze[5][5],prev[5][5];
int que[32];
int qn;void print(int x,int y)
{
if(prev[x][y]!=-2)
{
print(prev[x][y]>>3,prev[x][y]&7);
}
printf("(%d, %d)\n",x,y);
}int main()
{
int i,j,cx,cy,nx,ny;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
scanf("%d",&maze[i][j]);
}
}
memset(prev,-1,sizeof(prev));
prev[0][0]=-2;
que[0]=0;
qn=1;
for(i=0;i<qn;i++)
{
cx=que[i]>>3;
cy=que[i]&7;
for(j=0;j<4;j++)
{
nx=cx+dx[j];
ny=cy+dy[j];
if((nx>=0)&&(nx<5)&&(ny>=0)&&(ny<5)&&(maze[nx][ny]==0)&&(prev[nx][ny]==-1))
{
prev[nx][ny]=(cx<<3)|cy;
que[qn++]=(nx<<3)|ny;
if((nx==4)&&(ny==4))
{
print(nx,ny);
return 0;
}
}
}
}
return 0;
}