BFS之最简单的迷宫问题（并打印路径）

问题描述：给出迷宫的大小n,m，输入迷宫的信息，1表示该点可走，0表示该点是死胡同，问你从起点到终点是否有路？？？

#include <iostream>#include <queue>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>using namespace std;const int maxn=1000;const int inf=100;struct no{    int x,y;    int value;} node[maxn][maxn];int n,m,ix,iy;int beg_x,beg_y,end_x,end_y;int direction[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};int last[maxn],v,u;vector<int> nodes;queue<no> q;int flag=1;void bfs(int row,int col){    q.push(node[row][col]);    while(!q.empty())    {        no top = q.front();        u=top.x*inf+top.y;        v=u;        q.pop();        if(top.x==end_x && top.y==end_y)        {            flag=0;            for(;;)            {                //cout<<v/10<<" "<<v%10<<endl;                nodes.push_back(v);                if(last[v]==beg_x*inf+beg_y)                    break;                v=last[v];            }            nodes.push_back(beg_x*inf+beg_y);            cout<<"路径存在"<<endl;            return;        }        if(top.x>=0 && top.x<n && top.y>=0 && top.y<m && top.value==1)        {            for(int i=0; i<4; i++)            {                ix=top.x+direction[i][0];                iy=top.y+direction[i][1];                if(ix>=0 && ix<n && iy >=0 && iy<m && node[ix][iy].value==1)                {                    v=inf*(ix)+iy;                    q.push(node[ix][iy]);                    node[ix][iy].value=0;                    last[v]=u;                }            }        }        top.value=0;    }}int main(int argc, char* argv[]){    cout<<"请输入迷宫的长和宽:"<<endl;    cin>>n>>m;    cout<<"请输入迷宫n*m，1表示该点可以通过，0表示障碍物"<<endl;    for(int i=0; i<n; i++)        for(int j=0; j<m; j++)            cin>>node[i][j].value;    for(int i=0; i<n; i++)        for(int j=0; j<m; j++)        {            node[i][j].x=i;            node[i][j].y=j;        }    cout<<"请输入迷宫的起点(beg_x,beg_y)和终点(end_x,end_y)"<<endl;    cin>>beg_x>>beg_y>>end_x>>end_y;    bfs(beg_x,beg_y);    if(flag)        cout<<"路径不存在"<<endl;    else    {        cout<<"路径如下:"<<endl;        while(!nodes.empty())        {            cout<<"("<<nodes.back()/inf<<","<<nodes.back()%inf<<")"<<" ";            nodes.pop_back();        }    }    return 0;}