题目链接
题解：本体数据范围较小，暴力搜索即可解决问题。注意在搜索时，由于有两个出发点，要将两个出发点同时塞进搜索的队列中去，在进行搜索，就可以同时计算两个起点的搜索。
代码如下：
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <vector> #include <queue> using namespace std; const int maxn = 10 + 5; char map1[maxn][maxn]; int p1,p2,q1,q2; struct InQ{ int x; int y; int len; InQ(int x1 = 0,int y1 = 0,int len1 = 0) {x = x1;y = y1;len = len1;} }; int numg; int ans; int n,m; int dx[] = {0,0,-1,1}; int dy[] = {-1,1,0,0}; int vis[maxn][maxn]; char c; queue<InQ> q; void bfs(){ int maxv = 0,cnt = 0; memset(vis,0,sizeof(vis)); while(!q.empty()) q.pop(); q.push(InQ(p1,q1,0));vis[p1][q1] = 1;cnt++; q.push(InQ(p2,q2,0));vis[p2][q2] = 1;cnt++; while(!q.empty()){ InQ e = q.front();q.pop(); int x = e.x,y = e.y; for(int i = 0;i < 4;i++){ int nx = e.x + dx[i],ny = e.y + dy[i]; if(nx > 0 && nx <= n && ny > 0 && ny <= m && map1[nx][ny] == '#' && !vis[nx][ny]) { vis[nx][ny] = 1; q.push(InQ(nx,ny,e.len + 1)); cnt++; maxv = max(maxv,e.len + 1); } } } if(cnt >= numg) ans = min(ans,maxv); } char s[maxn]; int main() { int kase;scanf("%d",&kase); for(int T = 1;T <= kase;T++){ numg = 0;ans = 1000000; printf("Case %d: ",T); scanf("%d%d",&n,&m); c = getchar(); for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ scanf("%c",&map1[i][j]); if(map1[i][j] == '#') numg++; } c = getchar(); } for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ if(map1[i][j] != '#') continue; p1 = i;q1 = j; for(int i2 = i;i2 <= n;i2++){ for(int j2 = 1;j2 <= m;j2++){ if(i2 == i && j2 < j) continue; if(map1[i2][j2] != '#') continue; p2 = i2;q2 = j2; bfs(); } } } } if(ans == 1000000) printf("-1\n"); else printf("%d\n",ans); } return 0; }