灭火

点击量:40

火会蔓延,人被火追着跑,能否跑出边界的问题。

bfs火之后bfs人,或火和人放在一个队列里面bfs

坑是没有火的情况,如果从0更新火势图而不是inf开始,那么可能造成没火不能跑的情况。

/*=============================================================================
#
# Author: svtter - svtter@qq.com
#
# QQ : 57180160
#
# Last modified: 2015-05-04 09:50
#
# Filename: 11634.cpp
#
# Description: 
#
=============================================================================*/
#include <iostream>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <cmath>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
#define CR printf("\n")
const double PI = acos(-1.0);
const int maxn = 1010;
char g[maxn][maxn];
int gex[maxn][maxn];
bool vis[maxn][maxn];
int r, c;
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};
struct Node {
    int i, j, t;
    Node() {}
    Node(int i, int j, int t):i(i), j(j), t(t){}
};
inline int judge(int x, int y)
{
    return x >= 0 && x < r && y >= 0 && y < c;
}
void init(queue <Node> &q) {
    Node temp, next;
    int nx, ny;
    while(!q.empty()) {
        temp = q.front(), q.pop();
        temp.t++;
        for(int i = 0; i < 4; i++) {
            nx = temp.i + dx[i];
            ny = temp.j + dy[i];
            if(g[nx][ny] != '#' && judge(nx, ny) && gex[nx][ny] > temp.t) {
                next.i = nx;
                next.j = ny;
                next.t = temp.t;
                gex[nx][ny] = temp.t;
                q.push(next);
            }
        }
    }
}
int bfs(queue <Node> &q) {
    Node t, n;
    int nx, ny;
    while(!q.empty()) {
        t = q.front(), q.pop();
        if(t.i == r-1 || t.j == c-1 || t.i == 0 || t.j == 0) return t.t;
        t.t ++;
        for(int i = 0; i < 4; i++)
        {
            nx = t.i + dx[i];
            ny = t.j + dy[i];
            if(!vis[nx][ny] && gex[nx][ny] > t.t && judge(nx, ny))
            {
                n.i = nx, n.j = ny, n.t = t.t;
                vis[nx][ny] = 1;
                q.push(n);
            }
        }
    }
    return 0;
}
int main()
{
#ifdef DEBUG
    freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int t;
    scanf("%d", &t);
    queue <Node> q;
    while(t--) {
        while(!q.empty()) q.pop();
        scanf("%d%d", &r, &c);
        MEM(vis); Node joe;
        memset(gex, INF, sizeof(gex));
        for(int i = 0; i < r; i++)
            scanf("%s", g[i]);
        for(int i = 0; i < r; i++)
        {
            for(int j = 0;j < c;j ++) {
                if(g[i][j] == 'F')
                {
                    vis[i][j] = 1;
                    gex[i][j] = 1;
                    q.push(Node(i, j, 1));
                }
                else if(g[i][j] == 'J')
                {
                    vis[i][j] = 1;
                    joe = Node(i, j, 1);
                }
                else if(g[i][j] == '#') vis[i][j] = 1;
            }
        }
        init(q);
        q.push(joe);
        int ans = bfs(q);
        if(ans == 0) puts("IMPOSSIBLE");
        else printf("%d\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注