andyli

题解 UVA11624 【Fire!】
如果没有火,那么本题是一个标准的迷宫问题,可以用$BFS$解决。加上了火,难度增加了多少呢 ?其实没多少。注意,火...
扫描右侧二维码阅读全文
24
2019/06

题解 UVA11624 【Fire!】

如果没有火,那么本题是一个标准的迷宫问题,可以用$BFS$解决。加上了火,难度增加了多少呢 ?其实没多少。注意,火是不会自动熄灭的,因此只要某个格子在某时刻起火了,以后将一直如此。所以只需要预处理每个格子起火的时间,在$BFS$扩展结点的时候加一个条件判断,当到达新结点时该格子没着火才真的把这个新结点加到队列中。
最后需要考虑一下如何求出每个格子起火的时间,其实这也是个最短路问题,只不过起点不是一个,而是多个(所有初始的着火点)。这只需要在初始化队列时把所有着火点都放进去即可。
两个步骤的时间复杂度均为$O(RC)$。
去除模板后代码如下:

const int dir[][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, maxn = 1005;

char A[maxn][maxn];
int t[maxn][maxn], vis[maxn][maxn], r, c, bx, by;

using pii = pair<int, int>;
queue<pii> q;
bool isvaild(int x, int y)
{
    return x >= 0 && x < r && y >= 0 && y < c;
}

int bfs(int (*pArr)[1005])
{
    while (!q.empty())
    {
        auto fr = q.front();
        q.pop();
        if (pArr == vis && (!fr.first || !fr.second || fr.first == r - 1 || fr.second == c - 1))            return pArr[fr.first][fr.second];
        for (int i = 0; i < 4; i++)
        {
            int nx = fr.first + dir[i][0], ny = fr.second + dir[i][1];
            if (isvaild(nx, ny) && pArr[nx][ny] == -1)
            {
                if ((pArr == vis && pArr[fr.first][fr.second] + 1 >= t[nx][ny] && t[nx][ny] != -1) || A[nx][ny] == '#')
                    continue;
                pArr[nx][ny] = pArr[fr.first][fr.second] + 1;
                q.push(pii(nx, ny));
            }
        }
    }
    return -1;
}
int main()
{
    int T;
    read(T);
    while (T--)
    {
        while (!q.empty())
            q.pop();
        read(r, c);
        memset(t, -1, sizeof(t));
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                if ((A[i][j] = getchigws()) == 'F')
                    q.push(pii(i, j)), A[i][j] = '.', t[i][j] = 0;
                else if (A[i][j] == 'J')
                    bx = i, by = j, A[i][j] = '.';
        bfs(t);
        memset(vis, -1, sizeof(vis));
        q.push(pii(bx, by));
        vis[bx][by] = 0;
        int ans = bfs(vis);
        if (ans == -1)
            writeln("IMPOSSIBLE");
        else
            writeln(ans + 1);
    }
    return 0;
}
Last modification:June 25th, 2019 at 11:29 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment