UVA 11624 Fire! bfs

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=103921#problem/J
题意和思路见代码注释吧~~ 粗暴的两个bfs。。还真是可以~~
只用一个bfs 应该就是可以的。但是我没有想开~~也没研究~~
  1 /*
  2   大意是一个地图，开始的时候有一个人，然后还有几个位置着火了，想问人能否逃出，如果能，最短时间是多少。
  3   开始想先以人为起点，bfs，计算出人到达每个位置的时间。然后以火苗为起点 计算出火最早蔓延的时间 比较一下。
  4   有些麻烦，好像都放在一个队列里就可以吗？好像是不行的，
  5  */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <queue>
 11 #define maxn 1000000
 12 using namespace std;
 13 
 14 int n, m;
 15 char mp[2100][2100];
 16 bool visPer[2100][2100], visFire[2100][2100];
 17 int stepPer[2100][2100];
 18 int stepFire[2100][2100];
 19 
 20 
 21 struct Node{
 22     int x;
 23     int y;
 24 };
 25 
 26 queue<Node>que;
 27 queue<Node>queper;
 28 
 29 int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
 30 
 31 bool checkPer(Node a) {
 32     if (a.x >=0 && a.x < n && a.y >= 0 && a.y < m && !visPer[a.x][a.y] && mp[a.x][a.y] != '#') {
 33         return true;
 34     }
 35     return false;
 36 }
 37 
 38 bool checkFire(Node a) {
 39     if (a.x >=0 && a.x < n && a.y >= 0 && a.y < m && !visFire[a.x][a.y] && mp[a.x][a.y] != '#') {
 40         return true;
 41     }
 42     return false;
 43 }
 44 
 45 void dfsPer() {
 46     while(!queper.empty()) {
 47         Node now = queper.front();
 48         queper.pop();
 49 
 50         for (int i=0; i<4; ++i) {
 51             Node temp;
 52             temp.x = now.x + dir[i][0];
 53             temp.y = now.y + dir[i][1];
 54            // cout << checkPer(temp) << "===" << stepPer[now.x][now.y] + 1 << endl;
 55             if (checkPer(temp) && stepFire[temp.x][temp.y] > stepPer[now.x][now.y] + 1) {
 56                 queper.push(temp);
 57                 visPer[temp.x][temp.y] = 1;
 58                 stepPer[temp.x][temp.y] = stepPer[now.x][now.y] + 1;
 59             }
 60         }
 61     }
 62 }
 63 
 64 
 65 
 66 void dfsFire() {
 67     while(!que.empty()) {
 68         Node now = que.front();
 69         que.pop();
 70 
 71         for (int i=0; i<4; ++i) {
 72             Node temp;
 73             temp.x = now.x + dir[i][0];
 74             temp.y = now.y + dir[i][1];
 75             if (checkFire(temp)) {
 76                 que.push(temp);
 77                 visFire[temp.x][temp.y] = 1;
 78                 stepFire[temp.x][temp.y] = stepFire[now.x][now.y] + 1;
 79             }
 80         }
 81     }
 82 }
 83 
 84 int main() {
 85     int t;
 86     cin >> t;
 87     while(t--) {
 88         cin >> n >> m;
 89         for (int i=0; i<n; ++i) {
 90             for (int j=0; j<m; ++j) {
 91                 stepFire[i][j] = maxn;
 92                 stepPer[i][j] = maxn;
 93             }
 94         }
 95         while(!que.empty()) {
 96             que.pop();
 97         }
 98         while(!queper.empty()) {
 99             queper.pop();
100         }
101         memset(visPer, 0, sizeof(visPer));
102         memset(visFire, 0, sizeof(visFire));
103 
104         Node per;
105         for (int i=0; i<n; ++i) {
106             for (int j=0; j<m; ++j) {
107                 cin >> mp[i][j];
108                 if (mp[i][j] == 'F') {
109                     Node now;
110                     now.x = i, now.y = j;
111                     que.push(now);
112                     stepFire[i][j] = 1;
113                     visFire[i][j] = 1;
114                 }
115                 else if (mp[i][j] == 'J') {
116                     per.x = i, per.y = j;
117                     visPer[i][j] = 1;
118                     stepPer[i][j] = 1;
119                     queper.push(per);
120                 }
121             }
122         }
123         dfsFire();
124         dfsPer();
125 
126         int stepmin = maxn;
127         for (int i=0; i<n; ++i) {
128             stepmin = min(stepmin, stepPer[i][0]);
129             stepmin = min(stepmin, stepPer[i][m-1]);
130         }
131 
132         for (int i=0; i<m; ++i) {
133             stepmin = min(stepmin, stepPer[0][i]);
134             stepmin = min(stepmin, stepPer[n-1][i]);
135         }
136 
137         if (stepmin == maxn) {
138             cout << "IMPOSSIBLE
";
139         }
140         else cout << stepmin << endl;
141      }
142     return 0;
143 }
View Code