(C++)POJ-3984——迷宮を歩く(広さ優先アルゴリズム)

タイトルの説明
地図によると、法陣は四角く、縦横は5里で、地図上では5*5の行列を簡略化し、0または1だけで構成されている.このうち、0は歩ける道、1は通行止めのバリアを示す.左上角と右下角はそれぞれアレイの入口と出口であり、この2つの位置の数字は0に保証されている.地図を手に入れた以上、法陣を解くのは難しくない.今、小太りは法陣を出たいだけでなく、最短のルートで法陣を出る方法も知りたい.
input
入力は5× 5の2次元配列は,0,1の2つの数字のみからなり,法陣地図を表す.
output
左上から右下への最短経路が順次通過する座標を示す複数行を出力します.データは一意の解を保証します.
テーマ解説
明らかに,この問題は広さ優先探索(BFS)を用いて最短経路を見つける必要があり,唯一注意すべき点は,この経路の長さではなく,問題がこの経路を出力することを要求することであるため,構造体配列parent[N][N]を用いて,歩く経路の各点の前の点を保存することができる.このように、タイトル通りに始点から終点まで行くと、経路を出力するには逆出力が必要になるので、便宜上、終点から検索し、始点まで検索することで、正しい経路を直接得ることができます.
ソースコード(AC可)

#include
#include
#include
using namespace std;
int g[7][7];
int visit[7][7];
struct Point
{
    int x;
    int y;
    Point(){};//        
    Point(int _x,int _y):x(_x),y(_y){};//         
};
Point parent[7][7];
bool bfs(Point &pb,Point &pe)
{
    queue<Point> que;
    int run[][2]={
    {0,-1},{0,1},{1,0},{-1,0}
    };  //      
    parent[pb.x][pb.y]=pb;//       
    que.push(pb);
    while(!que.empty())
    {
        Point temp=que.front();//         true
        que.pop();
        visit[temp.x][temp.y]=1;
        if(temp.x==pe.x&&temp.y==pe.y)
            return true;
        for(int i=0;i<4;++i)
        {
            Point temp2(temp.x+run[i][0],temp.y+run[i][1]);
            if(g[temp2.x][temp2.y]==0&&visit[temp2.x][temp2.y]==0)
            {
                que.push(temp2);//            
                parent[temp2.x][temp2.y]=temp;//           
            }

        }
    }
    return false;
}
int main()
{
    for(int i=0;i<7;++i)
        g[0][i]=1;
    for(int i=0;i<7;++i)
        g[i][0]=1;
    for(int i=0;i<7;++i)
        g[6][i]=1;
    for(int i=0;i<7;++i)
        g[i][6]=1;
    while(cin>>g[1][1])
    {
        memset(visit,0,sizeof(visit));
        for(int i=1;i<=5;++i)
            for(int j=1;j<=5;++j)
        {
            if(i==1&&j==1)
                continue;
            else
                cin>>g[i][j];
        }
        Point g_begin(1,1),g_end(5,5);
        if(bfs(g_end,g_begin))
        {
            Point a(1,1);
            cout<<"(0, 0)"<<endl;
            while(a.x!=5||a.y!=5)
            {
                a=parent[a.x][a.y];
                cout<<'('<<a.x-1<<", "<<a.y-1<<')'<<endl;

            }
        }
        /*if(bfs(g_begin,g_end))
            cout<
    }
}