UVA 11624 Fire！

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

给出一张地图，J表示Joe所在位置，F表示着火的位置，可能有多个着火点, #表示障碍物，人和火都不能通过障碍物。人可以横向或纵向走，火每秒向横向和纵向蔓延一个网格，问人是否可以逃出，若可以，最少需要花多少时间？

分别求出人到达每个网格的时间 和 火到达每个网格的时间，比较二者到达地图边缘的时间，若人到达边缘的时间小于火，则可以逃出。

#include
#include
#include
#include
#include
#define pii pair
#include
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e3 + 7;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int m, n;
int maze[MAXN][MAXN];
int sx, sy;
int costByJoe[MAXN][MAXN], costByFire[MAXN][MAXN];
int vis[MAXN][MAXN];
int min_ans = INF;
void get_ans()
{for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(i == 0 || j == 0 || i == m - 1 || j == n - 1){if(maze[i][j]){if(costByFire[i][j] > costByJoe[i][j]){min_ans = min(min_ans, costByJoe[i][j]);}}}}}
}
void bfs(int x, int y, int cost[][1007], int flag)
{for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){cost[i][j] = INF;vis[i][j] = 0;}}queue<pii> q;if(flag) // 人{q.push(pii(x, y));vis[x][y] = 1;cost[x][y] = 1;}else // 火{for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(maze[i][j] == 2){q.push(pii(i, j));vis[i][j] = 1;cost[i][j] = 1;}}}}while(!q.empty()){pii now = q.front(); q.pop();for(int i = 0; i < 4; i++){int nx = now.first + dir[i][0];int ny = now.second + dir[i][1];if(nx >= 0 && nx < m && ny >= 0 && ny < n&& maze[nx][ny] && !vis[nx][ny]){vis[nx][ny] = 1;cost[nx][ny] = cost[now.first][now.second] + 1;q.push(pii(nx, ny));}}}}
int main()
{int T;cin >> T;while(T--){min_ans = INF;memset(maze, 0, sizeof(maze));string s;cin >> m >> n;for(int i = 0; i < m; i++){cin >> s;for(int j = 0; j < n; j++){if(s[j] == '#') maze[i][j] = 0;else if(s[j] == '.') maze[i][j] = 1;else if(s[j] == 'F') maze[i][j] = 2;else if(s[j] == 'J'){sx = i; sy = j;maze[i][j] = 1;}}}bfs(sx, sy, costByJoe, 1);bfs(sx, sy, costByFire, 0);get_ans();if(min_ans == INF) cout << "IMPOSSIBLE" << endl;else cout << min_ans << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！