POJ 3984 迷宫问题 bfs 难度:0

http://poj.org/problem?id=3984

典型的迷宫问题,记录最快到达某个点的是哪个点即可

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int maxn=10;

const int inf=0x3fffffff;

struct pnt {

        int x,y;

        pnt(){x=y=0;}

        pnt(int tx,int ty){x=tx,y=ty;}

};

int maz[maxn][maxn];

int step[maxn][maxn];

pnt from[maxn][maxn];

int n,m;

queue<int> que;

const int dx[8]={0,0,1,-1,1,1,-1,-1};

const int dy[8]={1,-1,0,0,1,-1,1,-1};

bool in(int x,int y){

        return x>=0&&x<n&&y>=0&&y<m;

}

void bfs(int sx,int sy){

        while(!que.empty())que.pop();

        memset(step,0x3f,sizeof(step));

        step[sx][sy]=0;

        que.push(sx*maxn+sy);

        while(!que.empty()){

                int x=que.front()/maxn,y=que.front()%maxn;que.pop();

                if(x==4&&y==4)break;

                for(int i=0;i<4;i++){

                        int tx=x+dx[i],ty=y+dy[i];

                        if(in(tx,ty)&&maz[tx][ty]!=1&&step[tx][ty]>step[x][y]+1){

                                step[tx][ty]=step[x][y]+1;

                                from[tx][ty]=pnt(x,y);

                                que.push(tx*maxn+ty);

                        }

                }

        }

}

pnt heap[maxn*maxn];int hlen;

int main(){

        n=5,m=5;

        for(int i=0;i<n;i++){

                for(int j=0;j<m;j++){

                        scanf("%d",maz[i]+j);

                }

        }

        bfs(0,0);

        pnt ask=pnt(4,4);

        heap[hlen++]=ask;

        do{

                ask=from[ask.x][ask.y];

                heap[hlen++]=ask;

        }while(ask.x!=0||ask.y!=0);

        for(int i=hlen-1;i>=0;i--){

                printf("(%d, %d)\n",heap[i].x,heap[i].y);

        }

        return 0;

}