定义一个二维数组：

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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

一个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

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

//update：2019蓝桥杯原题变式

BFS经典题。需要在结构体中定义c记录当前下标，用f记录父节点下标。输出路径时由叶节点遍历到根节点，逆序输出。

#include<stdio.h>

#include<queue>

using namespace std;

int a[][],b[][],rx[],ry[];

int t[][]={{,},{,},{-,},{,-}};

struct Node{

    int x,y,s,f,c;

}node[];

int main()

{

    int c,tx,ty,f,i,j;

    queue<Node> q;

    for(i=;i<=;i++){

        for(j=;j<=;j++){

            scanf("%d",&a[i][j]);

        }

    }

    node[].x=;

    node[].y=;

    node[].s=;

    node[].f=;

    node[].c=;

    b[][]=;

    q.push(node[]);

    c=;f=;

    while(q.size()){

        for(i=;i<;i++){

            c++;

            tx=q.front().x+t[i][];

            ty=q.front().y+t[i][];

            if(tx<||ty<||tx>||ty>) continue;

            if(a[tx][ty]==&&b[tx][ty]==){

                b[tx][ty]=;

                node[c].x=tx;

                node[c].y=ty;

                node[c].s=q.front().s+;

                node[c].f=q.front().c;

                node[c].c=c;

                q.push(node[c]);

            }

            if(tx==&&ty==){

                int cc=c;

                for(j=node[c].s+;j>=;j--){

                    rx[j]=tx-;

                    ry[j]=ty-;

                    cc=node[cc].f;

                    tx=node[cc].x;

                    ty=node[cc].y;

                }

                for(j=;j<=node[c].s+;j++){

                    printf("(%d, %d)\n",rx[j],ry[j]);

                }

                f=;

                break;

            }

        }

        if(f==) break;

        q.pop();

    }

    return ;

}