Fire! (UVA - 11624)

题面

img

思路

先跑一次bfs求出火蔓延到每一格的时间,再以此为限制对人跑bfs求解,注意有多个起火点

代码

  1using namespace std;
  2typedef long long ll;
  3const int inf = 0x3f3f3f3f;
  4const int N = 1e3+5;
  5
  6char b[N][N] = {{0}};
  7bool vis[N][N] = {{0}};
  8int t[N][N] = {{0}};
  9int T, n, m, ans = 0;
 10
 11int dx[] = { 1, -1,  0,  0};
 12int dy[] = { 0,  0,  1, -1};
 13
 14struct F {
 15    int x, y;
 16    int step;
 17};
 18
 19struct P {
 20    int x, y;
 21    int step;
 22};
 23queue<F> f;
 24
 25void pre() {
 26    memset(vis, 0, sizeof(vis));
 27    while(!f.empty()) {
 28        F tf = f.front();
 29        f.pop();
 30
 31        F nf = tf;
 32        for(int i=0; i<4; i++) {
 33            int x = nf.x = tf.x+dx[i];
 34            int y = nf.y = tf.y+dy[i];
 35
 36            if(x<0 || x>=n || y<0 || y>=m) {
 37                continue;
 38            }
 39
 40            if(!vis[x][y] && b[x][y]=='.') {
 41                nf.step = tf.step+1;
 42                f.push(nf);
 43                vis[x][y] = 1;
 44                t[x][y] = nf.step;
 45            }
 46        }
 47    }
 48}
 49
 50bool bfs(int x, int y) {
 51    memset(vis, 0, sizeof(vis));
 52
 53    P sp;
 54    sp.x = x;
 55    sp.y = y;
 56    sp.step = 0;
 57
 58    queue<P> q;
 59    q.push(sp);
 60    vis[x][y] = 1;
 61
 62    while(!q.empty()) {
 63        P tp = q.front();
 64        q.pop();
 65
 66        P np = tp;
 67        for(int i=0; i<4; i++) {
 68            int x = np.x = tp.x+dx[i];
 69            int y = np.y = tp.y+dy[i];
 70
 71            if(x<0 || x>=n || y<0 || y>=m) {
 72                ans = tp.step+1;
 73                return true;
 74            }
 75
 76            if(!vis[x][y] && b[x][y]=='.' && tp.step+1<t[x][y]) {
 77                np.step = tp.step+1;
 78                q.push(np);
 79                vis[x][y] = 1;
 80            }
 81        }
 82    }
 83    return false;
 84}
 85
 86int main(void) {
 87    scanf("%d", &T);
 88    for(int cs=1; cs<=T; cs++) {
 89        memset(t, inf, sizeof(t));
 90        scanf("%d%d", &n, &m);
 91        int x, y;
 92        for(int i=0; i<n; i++) {
 93            for(int j=0; j<m; j++) {
 94                scanf(" %c", &b[i][j]);
 95                if(b[i][j]=='F') {
 96                    F sf;
 97                    sf.x = i;
 98                    sf.y = j;
 99                    sf.step = 0;
100                    t[i][j] = 0;
101                    f.push(sf);
102                } else if(b[i][j]=='J') {
103                    x = i;
104                    y = j;
105                }
106            }
107        }
108        pre();
109        if(bfs(x, y))
110            printf("%d\n", ans);
111        else
112            printf("IMPOSSIBLE\n");
113    }
114    return 0;
115}