uva11624 Fire! （bfs预处理）

题目链接：https://vjudge.net/problem/UVA-11624

题意：给一个1000×1000的矩阵，有几个着火点和Joe，着火点和Joe每个单位时间均移动一个单位，求Joe逃出的最短时间。

思路：

　　先预处理，对每一个Fire进行一次bfs，更新cnt[i][j]，它表示(i,j)的着火时间，注意多个Fire能到达(i,j)时要使cnt[i][j]最小，并且该bfs中的判断语句if(cnt[xx][yy]<=ss) continue能够避免走重复的路径，因此不用标记数组。得到cnt数组后，再对Joe进行一次bfs即可，需要标记数组vis。

AC代码：

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
int go[4][2]={-1,0,0,1,1,0,0,-1};
int T,n,m,jx,jy,cnt[1005][1005],vis[1005][1005];
char mp[1005][1005];
vector<PII> vc;

struct node{
    int x,y,s;
}tmp;

void bfs1(int x,int y){
    queue<node> que;
    cnt[x][y]=0;
    tmp.x=x,tmp.y=y,tmp.s=0;
    que.push(tmp);
    while(!que.empty()){
        node now=que.front();que.pop();
        int nx=now.x,ny=now.y,ns=now.s;
        for(int i=0;i<4;++i){
            int xx=nx+go[i][0],yy=ny+go[i][1],ss=ns+1;
            if(xx<=0||xx>n||yy<=0||yy>m||mp[xx][yy]=='#') continue;
            if(cnt[xx][yy]<=ss) continue;
            cnt[xx][yy]=ss;
            tmp.x=xx,tmp.y=yy,tmp.s=ss;
            que.push(tmp);
        }
    }
}

bool onborder(int x,int y){
    return x==1||x==n||y==1||y==m;
}

int bfs2(int x,int y){
    queue<node> que;
    tmp.x=x,tmp.y=y,tmp.s=0;
    que.push(tmp);
    vis[x][y]=1;
    while(!que.empty()){
        node now=que.front();que.pop();
        int nx=now.x,ny=now.y,ns=now.s;
        if(onborder(nx,ny)) return ns+1;
        for(int i=0;i<4;++i){
            int xx=nx+go[i][0],yy=ny+go[i][1],ss=ns+1;
            if(xx<=0||xx>n||yy<=0||yy>m||mp[xx][yy]=='#') continue;
            if(vis[xx][yy]) continue;
            if(cnt[xx][yy]<=ss) continue;
            vis[xx][yy]=1;
            tmp.x=xx,tmp.y=yy,tmp.s=ss;
            que.push(tmp);
        }
    }
    return -1;
}

int main(){
    scanf("%d",&T);
    while(T--){
        vc.clear();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j){
                cnt[i][j]=inf;
                vis[i][j]=0;
                scanf(" %c",&mp[i][j]);
                if(mp[i][j]=='J') jx=i,jy=j;
                if(mp[i][j]=='F') vc.push_back(make_pair(i,j));
            }
        for(int i=0;i<vc.size();++i)
            bfs1(vc[i].first,vc[i].second);
        int t=bfs2(jx,jy);
        if(t==-1)
            printf("IMPOSSIBLE
");
        else
            printf("%d
",t);
    }
    return 0;
}