K - 迷宫问题 POJ 3984 BFS路径输出

(4, 4)

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=30;
const int inf=200000;
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define For(i,n) for(int i=0;i<(n);i++)
template<class T>inline T read(T&x)
{
    char c;
    while((c=getchar())<=32);
    bool ok=false;
    if(c=='-')ok=true,c=getchar();
    for(x=0; c>32; c=getchar())
        x=x*10+c-'0';
    if(ok)x=-x;
    return x;
}
template<class T> inline void read_(T&x,T&y)
{
    read(x);
    read(y);
}
template<class T> inline void write(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
template<class T>inline void writeln(T x)
{
    write(x);
    putchar('\n');
}
//  -------IO template------
int a[6][6];
int d[6][6];
struct node
{
    int x,y;
    int id;
    node(int a,int b,int c){x=a;y=b;id=c;}
};
int dx[]={0,0,1,-1};
int dy[]={-1,1,0,0};
int p[maxn];
vector<node>v[maxn];
void bfs(int x,int y)
{
    queue<node> q;
    For(i,maxn)v[i].clear();
    q.push(node(x,y,0));
    memset(d,0,sizeof(d));
    memset(p,-1,sizeof(p));
    d[x][y]=1;
    p[0]=-1;
    int num=1;
    v[0].push_back(node(x,y,0));
    while(!q.empty())
    {
        node s=q.front();q.pop();

        if(s.x==4&&s.y==4)
        {
            stack<node>sa;
            for(int i=s.id;i!=-1;i=p[i])
               sa.push(v[i][0]);
            while(!sa.empty())
            {
                printf("(%d, %d)\n",sa.top().x,sa.top().y);
                sa.pop();
            }
            return;
        }
        For(i,4)
        {
            int xx=dx[i]+s.x;
            int yy=dy[i]+s.y;
            if(a[xx][yy]||d[xx][yy]||xx>=5||xx<0||yy>=5||yy<0)continue;
            q.push(node(xx,yy,num));
            d[xx][yy]=d[s.x][s.y]+1;
            p[num]=s.id;
            v[num].push_back(node(xx,yy,num));
            num++;
        }
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    int n,m,i,j,k,t;
    For(i,5)For(j,5)read(a[i][j]);
    bfs(0,0);
    return 0;
}

K - 迷宫问题 POJ 3984 BFS路径输出

原文：http://blog.csdn.net/u013167299/article/details/44649543