首页 > 代码库 > POJ 3984 迷宫问题 BFS+路径保存

POJ 3984 迷宫问题 BFS+路径保存

题目链接:

 

思路:STL果然不是万能的。。写了一个下午。。。 改用普通数组写一会便过了。。真坑。。 主要就是建立一个保存前驱的数组

 

代码:

  

    #include <iostream>    #include <cstdio>     #include <queue>     using namespace std;    int a[6][6];    int go[4][2] = {1,0,0,1,-1,0,0,-1};            struct node    {        int x;        int y;    }q[100];        int pre[100];        bool check(int x,int y)    {        if(x<0||x>4||y<0||y>4||a[x][y]==1)            return false;        else            return true;    }        void print(int a)    {        if(a==0)        {            cout<<"("<<q[0].x<<", "<<q[0].y<<")"<<endl;            return;         }         else        {            print(pre[a]);            cout<<"("<<q[a].x<<", "<<q[a].y<<")"<<endl;        }    }        int main()    {    //    freopen("data.txt","r",stdin);                for(int i=0;i<5;i++)        {            for(int j=0;j<5;j++)            {                cin>>a[i][j];            }        }                 int t;        int head = 0;        int tail = 1;                q[head].x = 0;        q[head].y = 0;                while(head!=tail)        {                if(q[head].x==4 && q[head].y==4)            {                break;            }                        for(int i=0;i<4;i++)            {                                if(check(q[head].x+go[i][0],q[head].y+go[i][1]))                {                     q[tail].x = q[head].x+go[i][0];                    q[tail].y = q[head].y+go[i][1];                    pre[tail] = head;                    a[q[head].x][q[head].y] = 1;                    tail++;                }            }            head++;        }            print(head);        return 0;    } 

 

POJ 3984 迷宫问题 BFS+路径保存