链接：

题目：

定义一个二维数组：

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

记录路径:

增加一个记录路径的结构体二维数组；

对于每一个点，记录下它是由哪个点到达的

即： p[x][y].x,

　　 p[x][y].y

分别记录到达(x,y)这个点的前一个点的横纵坐标

最后倒推回去即可获得路径

 

代码：

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct Point{    int x;    int y;}tmp,tmp2;int xf[4] = {
   0,0,1,-1};int yf[4] = {
   1,-1,0,0};int vis[100][100];int a[10][10];Point pre[10][10];Point ans[30];queue
         
          q;int bfs(int x0,int y0,int x,int y){    while(!q.empty())    {        q.pop();    }    memset(vis,0,sizeof(vis));    tmp.x = x0;    tmp.y = y0;    q.push(tmp);    vis[x0][y0] = 1;    while(!q.empty())    {        tmp = q.front();        q.pop();        for(int i = 0; i < 4; i++)        {            tmp2.x = tmp.x + xf[i];            tmp2.y = tmp.y + yf[i];            if(tmp2.x >= 0 && tmp2.x <= 4 && tmp2.y >= 0 && tmp2.y <= 4 &&               !vis[tmp2.x][tmp2.y] && a[tmp2.x][tmp2.y] == 0)            {                q.push(tmp2);                vis[tmp2.x][tmp2.y] = vis[tmp.x][tmp.y] + 1;                pre[tmp2.x][tmp2.y].x = tmp.x;                pre[tmp2.x][tmp2.y].y = tmp.y;            }        }        if(vis[x][y])        {            break;        }    }    return vis[x][y]-1;}int main(){    for(int i = 0 ;i < 5; i++)    {        for(int j = 0; j < 5;j++)        {            scanf("%d",&a[i][j]);        }    }　　 bfs(0,0,4,4);    /*int tt = bfs(0,0,4,4);    printf("%d\n",tt);*/    int lastx = 4,lasty = 4;    int xx,yy,num = 0;    while(lastx || lasty)    {        ans[num].x = lastx;        ans[num].y = lasty;        num++;        //xx和yy是中间变量，将走向pre[xx][yy]的横纵坐标赋给lastx 和 lasty        //再通过lastx和lasty赋值到一维结构体数组ans[]上，便于输出横纵坐标        xx = lastx;        yy = lasty;        lastx = pre[xx][yy].x;        lasty = pre[xx][yy].y;    }    for(int i = num;i>=0;i--)    {        printf("(%d, %d)\n",ans[i].x,ans[i].y);        //注意格式(%d, %d)中的“，”号，wa了一上午　　　//还有一点：POJ不允许使用#include
          
           这个头文件 } return 0;}