这个题真要好好说一下了,比赛的时候怎么过都过不了,压点总是出错(vis应该初始化为inf,但是我初始化成了-1....),wa了n次,后来想到完全可以避免这个问题,只要入队列的时候判断一下就行了.
由于数据比较小,所以可以暴力的去解,不过先判断一下联通块可以解决一小部分问题的.
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define inf 99999999
char maps[][];
int n,m,vis[][],go[][] = {,,-,,,,,-};
struct Pos
{
int x,y;
};
bool ok(Pos a)
{
return (a.x>= && a.x<n && a.y>= && a.y<m && maps[a.x][a.y] == '#');
}
queue<Pos>que;
int bfs(Pos f1,Pos f2)
{
while(!que.empty()) que.pop();
que.push(f1);
que.push(f2);
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
vis[i][j] = inf;
}
}
vis[f1.x][f1.y] = vis[f2.x][f2.y] = ;
while(!que.empty())
{
Pos now = que.front();
que.pop();
Pos nex;
for(int i = ; i < ; i++)
{
nex.x = now.x + go[i][];
nex.y = now.y + go[i][];
if(ok(nex) && vis[nex.x][nex.y] > vis[now.x][now.y] + )
{
vis[nex.x][nex.y] = vis[now.x][now.y] + ;
que.push(nex);
}
}
}
int maxv = -;
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
if(maps[i][j] == '#')
maxv = max(maxv,vis[i][j]);
}
}
return maxv;
}
int main()
{
int t,ca = ;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i = ; i < n; i++)
scanf("%s",maps[i]);
int cnt = ;
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
if(maps[i][j] == '#')
cnt++;
}
}
printf("Case %d: ",++ca);
if(cnt <= )
{
printf("%d\n",);
continue;
}
int ans = inf;
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
if(maps[i][j] == '#')
{
for(int k = ; k < n; k++)
{
for(int q = ; q < m; q++)
{
if(j == q && i == k) continue;
if(maps[k][q] == '#')
{
Pos f1,f2;
f1.x = i,f1.y = j;
f2.x = k,f2.y = q;
ans = min(ans,bfs(f1,f2));
}
}
}
}
}
}
if(ans == inf)
{
cout<<-<<endl;
}
else cout<<ans<<endl;
}
return ;
}