搜索第一篇（迷宫）

最基本的迷宫问题

使用BFS进行遍历，其实BFS可以全当作最短路径的退化版本，优点在于不需要事先构建图，每次找到邻接即可。

使用队列维持，每个点基本包含三个状态，白，灰，黑。表明未访问且未未入队，未访问但入队，访问过。

每次加入点来归约。

迷宫问题就是典型的图的搜索问题，我们可以采用栈来实现迷宫的深度搜索，从而找到一条路径，但是却不是从入口到出口的最短路径；寻找最短搜索路径通常的方法是用广度优先搜索，利用队列来完成的，找到末点就是最短的因为树层次结构的原因。一般图的广度优先搜索算法可以简单描述为：

Void BFS(Graph G){

初始化一个队列；

从G的初始点开始；

if （当前的结点是目标结点）   搜索结束；

   else 初始点进入队列；

do {

取队头结点，并产生其相邻结点；

if （产生的结点是目标结点）  {输出一个解；搜索结束；}

if (产生的结点是新结点)  新结点进队列

} while (队头<=队尾)；

}  // end_BFS

如果我们要得到所有的解，只需找到一个解后输出，并不结束循环就可以了。

附源代码：

#include 
#include 
#define N 10
int maps[N][N];
int state[N][N];
int values[N][N];
int queue1[100],queue2[100];
int dirt[4][2]={0,-1,0,1,-1,0,1,0};
int head,tail;
int mixnum;
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a>b?b:a;
}
void print(int x,int y,int n)//递归输出路径
{
if(n==-1)
return;
if(values[x-1][y] == n-1 )
print(x-1,y,n-1);
else
print(x,y-1,n-1);
printf("(%d, %d)\n",x,y);
}
void solve(int x,int y)
{

int m,n,num,i,j,k;
if(x<0||x>4||y<0||y>4|| head>tail)
return;
state[x][y]=1;
queue1[tail]=0;
queue2[tail]=0;
tail++;
while(head{
num=0;
for(i=0;i<4;i++)
{

m=x+dirt[i][0];
n=y+dirt[i][1];
if(m<0||m>4||n<0||n>4|| head>tail)
continue;
if(state[m][n] ==0 && maps[m][n]==0)//维护队列并计算数值，为了最后输出
queue1[tail]=m,queue2[tail]=n,state[m][n]=1,tail++,values[m][n]=min(values[m][n],values[x][y]+1);
}
state[x][y]=2;
head++;
x=queue1[head];
y=queue2[head];

}
print(4,4,values[4][4]);
}

int main()
{
int i,j,k;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
scanf("%d",maps[i]+j),values[i][j]=0xffff;//附个大值，因为后面每次min
values[0][0]=0;
solve(0,0);


return 0;
}