UVA11624 Fire!(BFS)

题目链接。

分析：

先用BFS将所有的火能到达的时间计算出来，然后再一次BFS，计算最短路径。要求人每到一个方格的时间，必须小于该方格的着火时间。直到走到边界。

注意：

WA很多次。。后来想出来了。少考虑了一种情况，那就是人一开始就在边界的情况。

AC代码如下：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <queue>
#include <map>

using namespace std;

const int maxn = 1000 + 10;
const int INF = 1<<27;

struct node{
    int x, y, cur;
    node(int x, int y, int cur):x(x), y(y), cur(cur) {}
};

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

char G[maxn][maxn];
bool vis[maxn][maxn];
int cost[maxn][maxn], n, m;

queue<node> q;

void init(){
    memset(vis, false, sizeof(vis));
    while(!q.empty()) q.pop();
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cost[i][j] = INF;
        }
    }
}

void init_fire_time(){
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int t = q.front().cur;
        q.pop();
        for(int d=0; d<4; d++){
            int nx = x + dx[d];
            int ny = y + dy[d];
            if(nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx][ny] && G[nx][ny] == '.'){
                q.push(node(nx, ny, t+1));
                vis[nx][ny] = true;
                cost[nx][ny] = t+1;
            }
        }
    }
}

int bfs(int x, int y){
    while(!q.empty()) q.pop();

    q.push(node(x, y, 0));
    vis[x][y] = 1;
    while(!q.empty()){
        x = q.front().x;
        y = q.front().y;
        int t = q.front().cur;
        q.pop();
        for(int d=0; d<4; d++){
            int nx = x+dx[d];
            int ny = y+dy[d];
            if(nx>=0 && nx<n && ny>=0 && ny<m && G[nx][ny] == '.' && !vis[nx][ny] && t+1<cost[nx][ny]){
                if(nx == 0 || ny == 0 || nx == n-1 || ny == m-1) return t+1;
                q.push(node(nx, ny, t+1));
                vis[nx][ny] = 1;
            }
        }
    }
    return -1;
}

int main(){
    int T, x, y;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        init();
        for(int i=0; i<n; i++) scanf("%s", G[i]);

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(G[i][j] == 'J') { x = i; y = j; }
                else if(G[i][j] == 'F'){
                    q.push(node(i, j, 0));
                    vis[i][j] = true;
                    cost[i][j] = 0;
                }
            }
        }

        init_fire_time();

        memset(vis, false, sizeof(vis));

        vis[x][y] = 1;
        if(x == 0 || y == 0 || x == n-1 || y == m-1) { printf("1\n"); continue; }

        int ans = INF;
        ans = bfs(x, y);

        if(ans == -1)
            printf("IMPOSSIBLE\n");
        else
            printf("%d\n",ans+1);
    }

    return 0;
}

后来网上查了查。发现了一种其他的写法，不用单独考虑人一开始在边界的情况。那就是记录到达所有点的最短时间。然后找出边界点中到达时间最小的。然后我就按着思路把代码改了改。

AC代码如下：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <queue>
#include <map>

using namespace std;

const int maxn = 1000 + 10;
const int INF = 1<<27;

struct node{
    int x, y, cur;
    node(int x, int y, int cur):x(x), y(y), cur(cur) {}
};

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

char G[maxn][maxn];
bool vis[maxn][maxn];
int cost[maxn][maxn], n, m;
int ans[maxn][maxn];

queue<node> q;

void init(){
    memset(vis, false, sizeof(vis));
    while(!q.empty()) q.pop();
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cost[i][j] = INF;
            ans[i][j] = INF;
        }
    }
}

void init_fire_time(){
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int t = q.front().cur;
        q.pop();
        for(int d=0; d<4; d++){
            int nx = x + dx[d];
            int ny = y + dy[d];
            if(nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx][ny] && G[nx][ny] == '.'){
                q.push(node(nx, ny, t+1));
                vis[nx][ny] = true;
                cost[nx][ny] = t+1;
            }
        }
    }
}

void bfs(int x, int y){
    while(!q.empty()) q.pop();

    q.push(node(x, y, 0));
    vis[x][y] = 1;
    while(!q.empty()){
        x = q.front().x;
        y = q.front().y;
        int t = q.front().cur;
        q.pop();
        for(int d=0; d<4; d++){
            int nx = x+dx[d];
            int ny = y+dy[d];
            if(nx>=0 && nx<n && ny>=0 && ny<m && G[nx][ny] == '.' && !vis[nx][ny] && t+1<cost[nx][ny]){
                q.push(node(nx, ny, t+1));
                vis[nx][ny] = 1;
                ans[nx][ny] = t+1;
            }
        }
    }
}

int main(){
    int T, x, y;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        init();
        for(int i=0; i<n; i++) scanf("%s", G[i]);

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(G[i][j] == 'J') { x = i; y = j; ans[i][j] = 0; }
                else if(G[i][j] == 'F'){
                    q.push(node(i, j, 0));
                    vis[i][j] = true;
                    cost[i][j] = 0;
                }
            }
        }

        init_fire_time();

        memset(vis, false, sizeof(vis));

        vis[x][y] = 1;
        bfs(x, y);

        int Ans = INF;
        for(int i = 0;i < n;i++){
            Ans = min(Ans,ans[i][0]);
            Ans = min(Ans,ans[i][m-1]);
        }
        for(int i = 0;i < m;i++){
            Ans = min(Ans,ans[0][i]);
            Ans = min(Ans,ans[n-1][i]);
        }

        if(Ans == INF) printf("IMPOSSIBLE\n");
        else printf("%d\n",Ans+1);
    }

    return 0;
}