題目鏈接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=103921#problem/I

bfs水題。好像還做過一次了。思路題意都見代碼吧~

1 /* 2 大意是給一個n*m的圖。#表示長草，.表示空著，開始可以同時點燃兩個格子里面的草，一秒鐘蔓延到上下左右相鄰的格子。 3 空格不會有火。不能隔著格子蔓延。問是否能夠讓草的區域全部著火。如果能輸出用的最少的時間。 4 不知道思路從哪里來的。暴力。先判斷有幾個連通區域。如果>2,不可能。=2 兩個區域分別找最短時間相加。=1.兩重循環找最短時間、 5 無腦。 6 無腦卡殼了。不知道怎么實現。首先是計算有幾個區域，廣搜？可以。然后 == 2計算最短時間的時候，廣搜一遍？然后=1 ，，依然是廣搜.可行就是覺得麻煩。 7 然后。小王sir果斷告訴了我新的思路。兩重循環任意兩個草的位置為起點，搜索，從所有可能的結果中找最小值就可以了。我T_T。 8 */ 9 10 #include <stdio.h> 11 #include <string.h> 12 #include <iostream> 13 #include <queue> 14 #define maxn 1000000 15 using namespace std; 16 17 struct Node { 18 int x, y; 19 }node[10000]; 20 21 queue<Node>que; 22 int vis[20][20]; 23 int step[20][20]; 24 int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; 25 int n, m; 26 int cnt; 27 bool viss[20][20]; 28 29 bool check(Node a) { 30 int x = a.x, y = a.y; 31 if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && viss[x][y]) { 32 return true; 33 } 34 return false; 35 } 36 37 bool checkAll() { 38 for (int i=0; i<cnt; ++i) { 39 if (step[node[i].x][node[i].y] == maxn) 40 return false; 41 } 42 return true; 43 } 44 45 46 int bfs(int ii, int jj) { 47 while(!que.empty()) { 48 que.pop(); 49 } 50 memset(vis, 0, sizeof(vis)); 51 52 for (int i=0; i<n; ++i) { 53 for (int j=0; j<m; ++j) { 54 step[i][j] = maxn; 55 } 56 } 57 que.push(node[ii]); 58 que.push(node[jj]); 59 vis[node[ii].x][node[ii].y] = 1; 60 vis[node[jj].x][node[jj].y] = 1; 61 step[node[ii].x][node[ii].y] = 0; 62 step[node[jj].x][node[jj].y] = 0; 63 64 while(!que.empty()) { 65 Node now = que.front(); 66 que.pop(); 67 for (int i=0; i<4; ++i) { 68 Node temp; 69 temp.x = now.x + dir[i][0]; 70 temp.y = now.y + dir[i][1]; 71 if (check(temp)) { 72 que.push(temp); 73 vis[temp.x][temp.y] = 1; 74 step[temp.x][temp.y] = step[now.x][now.y] + 1; 75 } 76 } 77 if (checkAll()) break; 78 } 79 if (!checkAll()) return maxn; 80 int tempans = -1; 81 for (int i=0; i<cnt; ++i) { 82 tempans = max(step[node[i].x][node[i].y], tempans); 83 } 84 return tempans; 85 } 86 87 int main() { 88 int t; 89 char temp; 90 cin >> t; 91 int num = 0; 92 while(t--) { 93 Node now; 94 cnt = 0; 95 memset(viss, 0, sizeof(viss)); 96 cin >> n >> m; 97 for (int i=0; i<n; ++i) { 98 for (int j=0; j<m; ++j) { 99 cin >> temp; 100 if (temp == '#') { 101 now.x = i; 102 now.y = j; 103 viss[now.x][now.y] = 1; 104 node[cnt++] = now; 105 } 106 } 107 } 108 109 int ans = maxn; 110 for (int i=0; i<cnt; ++i) { 111 for (int j=0; j<cnt; ++j) { 112 ans = min(bfs(i, j), ans); 113 } 114 } 115 116 cout << "Case " << ++num << ": "; 117 if (ans == maxn) { 118 cout << -1 << endl; 119 } 120 else { 121 cout << ans << endl; 122 } 123 } 124 return 0; 125 } View Code

?

轉載于:https://www.cnblogs.com/icode-girl/p/5158972.html

總結

以上是生活随笔為你收集整理的FZU 2150 Fire Game bfs的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。