链接：http://acm.fzu.edu.cn/problem.php?pid=2150
题意：一个平面上有n堆草，两个人想在上面OOXX，所以要把草烧光（我也不知道为什么，题目这么说的），一个人只能烧一堆草，草烧着的话一个单位时间后会烧着它周围的草，当然如果它周围有草的话，如果草堆大于2个他们就不能烧完输出-1，输出至少要多长时间他们能把草烧完。注意两个人可以同时烧同一堆草。
拿到这题首先想到了森林火灾，是个bfs，我首先用dfs判断了一下草堆的个数，然后最长要多少时间，我鬼使神差的想成了dfs，dfs最长深度就是至少需要的时间，果断WA了，因为和深度无关，和横纵坐标差值有关，然后我又判断了一下横纵坐标差，继续WA，这下不知道错在哪了。又把题看了一遍，发现：两个人可以同时烧一堆草。。。。
不想重新写了，想来想去，dfs的确做不了，bfs也有特点，它是从两个点一起搜的，然后我把每个草堆的点存在了新的结构体数组中，枚举两两个点，结构体中记录时间，找最长的时间，然后再判断一下地图中草是否全部烧光，因为有可能两堆草枚举了同一堆的两个点，这样使得另一堆草没有烧，答案必然也不对，就没必要更新答案了。如果草都烧光了就更新答案。
不想多说了，漏看条件WA了一下午
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 810
#define eps 1e-7
#define INF 0x7FFFFFFF
typedef long long ll;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct node{
int x,y,step;
}mp[110];
queue<node> q;
int n, m, cnt;
int ans1;
char a[15][15];
int vis[15][15];
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
bool cango(int x,int y){
if(x<n&&x>=0&&y<m&&y>=0) return true;
return false;
}
void dfs(int x,int y){
vis[x][y] = 1;
int i, j;
for(i=0;i<4;i++){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(cango(xx,yy)&&a[xx][yy]=='#'&&!vis[xx][yy]){
dfs(xx,yy);
}
}
}
int main(){
int t, i, j, k = 1, cntk, flag;
scanf("%d",&t);
while(t--){
while(!q.empty()) q.pop();
cntk = 0;
memset(vis,0,sizeof(vis));
ans1 = 110;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++){
scanf("%s",a[i]);
for(j=0;j<m;j++){
if(a[i][j]=='#'){
mp[cntk].x = i;
mp[cntk].y = j;
cntk++;
}
}
}
cnt = 0;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(a[i][j]=='#'&&!vis[i][j]){
dfs(i,j);
cnt++;
}
}
}
if(cnt>2){
printf("Case %d: -1\n",k++);
continue;
}
int cnt1;
for(i=0;i<cntk;i++){
for(j=i;j<cntk;j++){
//cout<<mp[i].x<<mp[i].y<<endl;
cnt1 = 0;
flag = 0;
memset(vis,0,sizeof(vis));
vis[mp[i].x][mp[i].y] = 1;
vis[mp[j].x][mp[j].y] = 1;
mp[i].step = 0;
mp[j].step = 0;
q.push(mp[i]);
q.push(mp[j]);
while(!q.empty()){
//cout<<"aaaaaaaaaaa"<<endl;
node tt = q.front();
q.pop();
int ii;
for(ii=0;ii<4;ii++){
int ttx = tt.x + dir[ii][0];
int tty = tt.y + dir[ii][1];
if(cango(ttx,tty)&&a[ttx][tty]=='#'&&!vis[ttx][tty]){
vis[ttx][tty] = 1;
node temp;
temp.x = ttx;
temp.y = tty;
temp.step = tt.step+1;
q.push(temp);
}
}
if(tt.step>cnt1) cnt1 = tt.step;
}
for(int ii=0;ii<n;ii++){
for(int jj=0;jj<m;jj++){
if(a[ii][jj]=='#')
if(!vis[ii][jj]){
flag = 1;
break;
}
}
if(flag) break;
}
if(flag) continue;
if(cnt1<ans1) ans1 = cnt1;
}
}
printf("Case %d: %d\n",k++,(ans1==110)?-1:ans1);
}
return 0;
}
FZU--2150--Fire Game【BFS】,布布扣,bubuko.com
原文：http://blog.csdn.net/zzzz40/article/details/38122385