廣搜之迷宮問題

#include<iostream>
           

using namespace std;
struct node
{
    int x,y,pre;
};
node a[100];
int m[6][6];
int dx[]= {1,-1,0,0};
int dy[]= {0,0,1,-1};
int head,tail;
void print(int i)
{
    if(a[i].pre!=-1)
    {
        print(a[i].pre);
        cout<<"("<<a[i].x-1<<", "<<a[i].y-1<<")"<<endl;
    }
}
void bfs()
{
    a[0].x = 1;
    a[0].y=1;
    a[0].pre=-1;
    head=0;
    tail=1;
    while(head<tail)
    {
        int px = a[head].x;
        int py=a[head].y;
        for(int i=0; i<4; i++)
        {
            int endx = px+dx[i];int endy = py+dy[i];
            if(endx<=0||endx>5||endy<=0||endy>5||m[endx][endy])
                continue;
            else
            {
                m[endx][endy]=1;
                a[tail].x = endx;
                a[tail].y=endy;
                a[tail].pre=head;
                tail++;
            }
            if(endx==5&&endy==5)
                print(head);
        }
        head++;//隊首元素出隊列
    }
}
int main()
{
    for(int i=1; i<=5; i++)
        for(int j=1; j<=5; j++)
            cin >> m[i][j];
    cout<<"("<<0<<", "<<0<<")"<<endl;
    bfs();
    cout<<"("<<4<<", "<<4<<")"<<endl;
    return 0;
}
           

由于要求寫出路徑，是以結點必須記錄父親資訊。不能用stl的隊列，原因是pop()之後就找不到了，用數組實作，維護頭尾指針