UVA

Fire! (UVA - 11624) 题面 思路 先跑一次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}