题意：'#'表示草地，两个人在草地上点火，相邻的草地会烧起来，每烧一格等1秒，问最少要等几秒草地才烧完
分析：这题和UVA 11624 Fire!有点像，那题给定了两个点，这题两点不确定，取最小值。可以仿照11624的做法，两次BFS，第二次更新最小值，这样我跑了900多ms。后来发现不需要这样，枚举两个点，将它们一起入队，vis过的点一定已经是最优的，广搜的特点。
收获：1. 进一步理解BFS的过程 2. 差错能力有待提高 3. 写过的题一定要总结！(刚刷过专题！！！)
代码：
/************************************************
* Author :Running_Time
* Created Time :2015-8-23 12:40:49
* File Name :J.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 12;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
struct Node {
int x, y, step;
};
Node g[N*N];
char maze[N][N];
int d[N][N];
bool vis[N][N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int n, m, cnt, res; bool judge(int x, int y) {
if (x < 1 || x > n || y < 1 || y > m || vis[x][y] || maze[x][y] != '#') return false;
return true;
} void BFS(int sx, int sy, int ex, int ey) {
queue<Node> Q;
Q.push ((Node) {sx, sy, 0});
Q.push ((Node) {ex, ey, 0});
vis[sx][sy] = vis[ex][ey] = true;
while (!Q.empty ()) {
Node r = Q.front (); Q.pop ();
int x = r.x, y = r.y, step = r.step;
res = max (res, step);
for (int i=0; i<4; ++i) {
int tx = x + dx[i], ty = y + dy[i];
if (!judge (tx, ty)) continue;
vis[tx][ty] = true;
Q.push ((Node) {tx, ty, step + 1});
}
}
} bool check(void) {
for (int i=1; i<=cnt; ++i) {
int x = g[i].x, y = g[i].y;
if (!vis[x][y]) return false;
}
return true;
} int work(void) {
int ans = INF;
if (cnt <= 2) return 0;
for (int i=1; i<=cnt; ++i) {
for (int j=i+1; j<=cnt; ++j) {
memset (vis, false, sizeof (vis)); res = 0;
BFS (g[i].x, g[i].y, g[j].x, g[j].y);
if (check ()) ans = min (ans, res);
}
} if (ans == INF) return -1;
else return ans;
} int main(void) {
int T, cas = 0; scanf ("%d", &T);
while (T--) {
cnt = 0;
scanf ("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
scanf ("%s", maze[i] + 1);
for (int j=1; j<=m; ++j) {
if (maze[i][j] == '#') {
g[++cnt].x = i; g[cnt].y = j;
}
}
} printf ("Case %d: %d\n", ++cas, work ());
} return 0;
}