UVa 11624

题目链接：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=2671&mosmsg=Submission+received+with+ID+26578200

将所有着火点都放进队列中，依次拓展即可，处理出每个格子最早的着火时间

然后普通 (BFS) 求解 (Joe) 逃离的最短路线即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1010;
const int INF = 1000000007;

int T, n, m; 
char ch[maxn];

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

int a[maxn][maxn];
int d[maxn][maxn], f[maxn][maxn];
int sx, sy;

int vis[maxn][maxn];

struct Node{
	int x, y, t; // 0 J 1 F
	
	Node(int x, int y, int t): x(x), y(y), t(t){};
};

void bfs(){
	memset(f, 0x3f, sizeof(f));
	for(int i = 1 ; i <= n ; ++i){
		for(int j = 1 ; j <= m ; ++j){
			d[i][j] = INF;
		} 
	}
	memset(vis, 0, sizeof(vis));
	queue<Node> q;
	
	for(int i = 1 ; i <= n ; ++i){
		for(int j = 1 ; j <= m ; ++j){
			if(a[i][j] == 2) {
				q.push(Node(i, j, 1));
				f[i][j] = 0;
			}
		} 
	} 

	while(!q.empty()){
		Node p = q.front(); q.pop();
		
		if(vis[p.x][p.y]) continue;
		vis[p.x][p.y] = 1;
		
		for(int i = 0 ; i < 4 ; ++i){
			int x = p.x + dx[i], y = p.y + dy[i];
			if(x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && a[x][y] == 0){
				f[x][y] = f[p.x][p.y] + 1;						
				q.push(Node(x, y, p.t));
			}
		}
	}
	
	memset(vis, 0, sizeof(vis));
	while(!q.empty()) q.pop();
	
	q.push(Node(sx, sy, 0));
	d[sx][sy] = 0;
	
	while(!q.empty()){
		Node p = q.front(); q.pop();
		
		if(vis[p.x][p.y]) continue;
		vis[p.x][p.y] = 1;
		
		for(int i = 0 ; i < 4 ; ++i){
			int x = p.x + dx[i], y = p.y + dy[i];
			if(x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && f[x][y] > d[p.x][p.y] + 1 && a[x][y] == 0){
				d[x][y] = d[p.x][p.y] + 1;
				q.push(Node(x, y, 0));
			}
		}
	}
}

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d%d", &n, &m);
		for(int i = 1 ; i <= n ; ++i){
			scanf("%s", ch + 1);
			for(int j = 1 ; j <= m ; ++j){
				if(ch[j] == '#') a[i][j] = 1;
				else if(ch[j] == '.'){
					a[i][j] = 0;
				} else if(ch[j] == 'J'){
					sx = i, sy = j;
					a[i][j] = 0;
				} else{
					a[i][j] = 2;
				}
			}
		}
		
		bfs();
		
		int ans = INF;
		for(int i = 1 ; i <= n ; ++i){
			ans = min(ans, d[i][1]);
			ans = min(ans, d[i][m]);
		}
		for(int i = 1 ; i <= m ; ++i){
			ans = min(ans, d[1][i]);
			ans = min(ans, d[n][i]);
		}
		
		if(ans != INF) printf("%d
", ans + 1);
		else {
			printf("IMPOSSIBLE
");
		}
	}
	return 0;
}