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}