Description
定义一个二维数组：
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,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
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
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4) 分析：
本题为一迷宫，从左上方走到右下方经过的最短路线，典型的bfs问题 先到达就退出 主要是打印路线 可以用一个值来保存经过的最短路线然后倒向追踪打印路线
Ac代码：
#include <iostream>
#include<cstring>
using namespace std;
int top = -,under = ,visit[][],dir[][]={{-,},{,},{,},{,-}},queue[],a[][],v,s[];
void queue_push(int x)
{
queue[++top] = x;
}
int queue_pop()
{
return queue[under++];
}
int main()
{
int i,j;
for(i = ; i < ; i++)
{
for(j = ; j < ; j++)
{
cin>>a[i][j];
}
}
memset(visit,,sizeof(visit));
queue_push();
visit[][] = ;
while(under<=top)
{
v = queue_pop();
if(v == ) break;
int x = v/,y = v%;
for(int i = ;i < ;i++)
{
int px = x+dir[i][],py = y +dir[i][];
if(visit[px*+py][] == &&a[px][py] == &&px>=&&px<&&py>=&&py<)
{
queue_push(px*+py); //满足条件添加进数组
visit[px*+py][] = ; //标记已经经过此点
visit[px*+py][] = v; //保存路线
}
}
} for( i = ,s[] = ;s[i-] != ; i++ )
{
s[i] = visit[s[i-]][];
}
for( j = i- ;j >= ; j--)
{
cout<<"("<<s[j]/<<", "<<s[j]%<<")"<<endl;
}
return ;
}