UVA11624 Fire!

#.F

Sample Output
3
IMPOSSIBLE

//题意是，J在迷宫里，同时迷宫里有若干火源（数量大于等于1）同时火会周围蔓延，问人能否逃离，逃离就是有路可以到达边缘

//类似于双起点的BFS，可以看成多起点的搜索，先处理一下火能到的点得时间，在从人开始搜索

#include<bits/stdc++.h>
using namespace std;
const int maxn=1015;
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------
struct node
{
    int x,y;
    node(int a,int b)
    {
        x=a;
        y=b;
    }
};
int dx[]= {0,0,1,-1};
int dy[]= {1,-1,0,0};
int n,m;

char a[maxn][maxn];
int  d[maxn][maxn];
vector<node> v;

void bfs_F()//相当于多起点的搜索 BFS是一层一层的进行，正好达到了“同时”进行搜索的目标
{
    queue<node> q;
    int kk=v.size();
    For(i,kk)q.push(v[i]);
    while(!q.empty())
    {
        node s=q.front();
        q.pop();
        for(int i=0; i<4; i++)
        {
            int xx=dx[i]+s.x;
            int yy=dy[i]+s.y;
            if(xx>n||xx<0||yy>m||yy<0)continue;
            if(a[xx][yy]=='#')continue;
            if(d[xx][yy])continue;
            q.push(node(xx,yy));
            d[xx][yy]=d[s.x][s.y]+1;
        }
    }
}

int dd[maxn][maxn];
bool bfs_J(int x,int y)
{
    queue<node> q;
    q.push(node(x,y));
    memset(dd,0,sizeof(dd));
    dd[x][y]=1;
    while(!q.empty())
    {
        node s=q.front();
        q.pop();
        if(s.x==0||s.x==n-1||s.y==0||s.y==m-1)
        {
            printf("%d\n",dd[s.x][s.y]);
            return true;
        }
        for(int i=0; i<4; i++)
        {
            int xx=dx[i]+s.x;
            int yy=dy[i]+s.y;
            if(xx<0||yy<0||xx>n||yy>m)continue;
            if(a[xx][yy]=='#')continue;
            if(d[xx][yy]&&dd[s.x][s.y]+1>=d[xx][yy])continue;
            if(dd[xx][yy])continue;
            q.push(node(xx,yy));
            dd[xx][yy]=dd[s.x][s.y]+1;
            if(xx==0||xx==n-1||yy==0||yy==m-1)
            {
                printf("%d\n",dd[xx][yy]);
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int i,j,k,t;
    int T;
#ifndef ONLINE_JUDGE
    freopen("test.txt","r",stdin);
    freopen("Ab.txt","w",stdout);
#endif // ONLINE_JUDGE
    read(T);
    while(T--)
    {
        read_(n,m);
        v.clear();
        int jx,jy,fx,fy;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                d[i][j]=0;
                scanf("%c",&a[i][j]);
                if(a[i][j]=='J')
                {
                    jx=i;
                    jy=j;
                }
                else if(a[i][j]=='F')
                {
                    v.push_back(node(i,j));
                    d[i][j]=1;
                }
            }
            getchar();
        }
        bfs_F();
        if(!bfs_J(jx,jy))
            printf("IMPOSSIBLE\n");
    }
    return 0;
}

UVA11624 Fire!

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