POJ - 3984 迷宫问题 

题目链接：

题目：

定义一个二维数组：

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 00 1 0 1 00 0 0 0 00 1 1 1 00 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广搜，详解见代码

//// Created by hanyu on 2019/7/7.//#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct node {    int i;    int j;};//结构体存储坐标int a[10][10];//输入的01矩阵node cun[50];//记录结果路径node p;//当前位置的状态queue
         
          qu;//将位置状况存入队列中int dir[4][2]={
   {
   1,0},{-1,0},{
   0,1},{
   0,-1}};//四个方向的移动int book[10][10];//判断是否走过int xx,yy,len;//xx下一位置的横坐标，yy下一纵位置的坐标，len记录走过的步数void bfs(){    len=0;//初始化步数为0    memset(book,0,sizeof(book));//初始化判断的数组    p.i=0;    p.j=0;//一开始坐标都为0    qu.push(p);//初试状态压入队列中    book[0][0]=1;//起始位置已经走过    while(!qu.empty())    {        p=qu.front();//当前位置的状态为队首        qu.pop();//删去队首        for(int i=0;i<4;i++)        {            xx=p.i+dir[i][0];//下一位置的横坐标            yy=p.j+dir[i][1];//下一位置的纵坐标            if(xx<0||xx>4||yy<0||yy>4)                continue;//防止越界            if(a[xx][yy]==0&&!book[xx][yy])//遇到0且该位置没有走过            {                book[xx][yy]=book[p.i][p.j]+1;//book下一位置值就是把book下标为现在位置的值+1，有效记录走过的步数                if(xx==4&&yy==4){
   //当走到终点时步数等于book该位置值                    len=book[xx][yy];                    break;                }                node new1;//新建一个结构体                new1.i=xx;                new1.j=yy;//下一坐标值存入结构体中                qu.push(new1);//将其存入该队列中            }        }    }    p.i=4;    p.j=4;    //此时位置为（4,4）    for(int i=len-1;i>=0;i--)    {        cun[i].i=p.i;        cun[i].j=p.j;//将路径倒着存入cun的数组中        for(int j=0;j<4;j++)//四个方向继续搜        {            xx=p.i+dir[j][0];            yy=p.j+dir[j][1];            if(xx<0||xx>4||yy<0||yy>4)                continue;            if((book[xx][yy]==book[p.i][p.j]-1))//如果下一步的值为现在的值减一，值就是步数            {                p.i=xx;//更新位置                p.j=yy;                break;            }        }    }    for(int i=0;i
          
           > a[i][j]; } } bfs(); return 0;}