火会蔓延,人被火追着跑,能否跑出边界的问题。
bfs火之后bfs人,或火和人放在一个队列里面bfs
坑是没有火的情况,如果从0更新火势图而不是inf开始,那么可能造成没火不能跑的情况。
/*============================================================================= # # Author: svtter - [email protected] # # 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[] = {, 1, -1, }; int dy[] = {1, , , -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 >= && x < r && y >= && 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 = ; 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 == || t.j == ) return t.t; t.t ++; for(int i = ; 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 ; } 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 = ; i < r; i++) scanf("%s", g[i]); for(int i = ; i < r; i++) { for(int j = ;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 == ) puts("IMPOSSIBLE"); else printf("%d\n", ans); } return ; }