4
3 3
.#.
###
.#.
3 3
.#.
#.#
.#.
3 3
...
#.#
...
3 3
###
..#
#.#
//题意是连通分量小于2的时候，任选两点（可以重合）开始，求最少的时间访问到所有的#位置，每步耗时1个单位，
//就是两个起点的同时搜索，程序里实际上还是交替进行搜索的，以此实现同时的搜索
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
using namespace std;
const int maxn=15;
const int inf=200000;
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define For(i,n) for(int i=0;i<(n);i++)
template<class T>inline T read(T&x)
{
char c;
while((c=getchar())<=32);
bool ok=false;
if(c=='-')ok=true,c=getchar();
for(x=0; c>32; c=getchar())
x=x*10+c-'0';
if(ok)x=-x;
return x;
}
template<class T> inline void read_(T&x,T&y)
{
read(x);
read(y);
}
template<class T> inline void write(T x)
{
if(x<0)putchar('-'),x=-x;
if(x<10)putchar(x+'0');
else write(x/10),putchar(x%10+'0');
}
template<class T>inline void writeln(T x)
{
write(x);
putchar('\n');
}
// -------IO template------
bool vis[maxn][maxn];
char G[maxn][maxn];
int n,m;
int dx[]= {1,-1,0,0};
int dy[]= {0,0,1,-1};
void dfs(int x,int y)
{
vis[x][y]=true;
for(int i=0; i<4; i++)
{
int xx=dx[i]+x;
int yy=dy[i]+y;
if(xx>=0&&xx<n&&yy>=0&&yy<m&&G[xx][yy]=='#'&&!vis[xx][yy])
{
dfs(xx,yy);
}
}
}
struct node
{
int x,y;
node(int a,int b)
{
x=a;
y=b;
}
};
int d[maxn][maxn];
int rec=1;
void bfs(int x,int y,int x1,int y1)
{
queue<node> q;
q.push(node(x,y));
q.push(node(x1,y1));
vis[x][y]=true;
vis[x1][y1]=true;
d[x][y]=0;
d[x1][y1]=0;
while(!q.empty())
{
node s=q.front();
q.pop();
for(int i=0; i<4; i++)
{
int xx=dx[i]+s.x;
int yy=dy[i]+s.y;
if(xx>=0&&xx<n&&yy>=0&&yy<m&&!vis[xx][yy]&&G[xx][yy]=='#')
{
vis[xx][yy]=true;
q.push(node(xx,yy));
d[xx][yy]=d[s.x][s.y]+1;
rec=max(rec,d[xx][yy]);
}
}
}
}
bool ok()
{
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(G[i][j]=='#'&&!vis[i][j])return false;
return true;
}
bool mmvis[maxn][maxn][maxn][maxn];//双起点的标记
int main()
{
int i,j,k,t;
int T;
#ifndef ONLINE_JUDGE
freopen("test.txt","r",stdin);
freopen("Ab.txt","w",stdout);
#endif // ONLINE_JUDGE
read(T);
int cas=1;
while(T--)
{
memset(G,0,sizeof(G));
read_(n,m);
for(i=0; i<n; i++)
for(j=0; j<m; j++)
cin>>G[i][j];
memset(vis,0,sizeof(vis));
int ans=0;
For(i,n)For(j,m)if(G[i][j]=='#'&&!vis[i][j])
{
dfs(i,j);
ans++;
}
//writeln(ans);
if(ans>2)ans=-1;
else
{
ans=inf;
memset(mmvis,false,sizeof(mmvis));
For(i,n)For(j,m)if(G[i][j]=='#')
{
For(u,n)For(v,m)if(G[u][v]=='#'&&!mmvis[i][j][u][v])
{
mmvis[i][j][u][v]=mmvis[u][v][i][j]=true;
memset(vis,0,sizeof(vis));
memset(d,0,sizeof(d));
rec=0;
bfs(i,j,u,v);
if(ok()&&rec<ans)ans=rec;
}
}
}
printf("Case %d: %d\n",cas++,ans);
}
return 0;
}
I - Fire Game FZU 2150 双起点的BFS
原文：http://blog.csdn.net/u013167299/article/details/44620201