枚举两点，然后同步BFS，看代码吧，很容易懂的。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #define Mod 1000000007 using namespace std; struct Point { int x,y; int step; }S; char mp[13][13]; int vis[13][13]; int n,m; int lef; int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; queue<Point> que; bool OK(int nx,int ny) { if(nx < n && nx >= 0 && ny < m && ny >= 0) return true; return false; } int BFS() { int maxi = 0; while(!que.empty()) //同步搜索 { int SIZE = que.size(); while(SIZE--) { Point tmp = que.front(); que.pop(); int nx = tmp.x; int ny = tmp.y; int step = tmp.step; maxi = max(maxi,step); Point now; for(int k=0;k<4;k++) { int kx = nx + dx[k]; int ky = ny + dy[k]; if(!OK(kx,ky) || vis[kx][ky]) continue; if(mp[kx][ky] == '#') { vis[kx][ky] = 1; now.x = kx; now.y = ky; now.step = step+1; que.push(now); lef--; } } } } if(lef == 0) return maxi; else return -1; } int main() { int t,cs = 1,i,j,k,h; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); int cnt = 0; for(i=0;i<n;i++) { scanf("%s",mp[i]); for(j=0;j<m;j++) if(mp[i][j] == '#') cnt++; } int flag = 0; int tag = Mod; for(i=0;i<n;i++) //第一个点 { for(j=0;j<m;j++) { if(mp[i][j] == '#') { for(k=i;k<n;k++) //第二个点 { for(h=(k==i?j:0);h<m;h++) { if(mp[k][h] == '#') { memset(vis,0,sizeof(vis)); S.x = i,S.y = j,S.step = 0; que.push(S); lef = cnt-1; vis[i][j] = 1; if(!(i==k&&j==h)) { S.x = k,S.y = h,S.step = 0; que.push(S); vis[k][h] = 1; lef--; } int res = BFS(); if(res != -1) { flag = 1; tag = min(tag,res); } } } } } } } if(flag) printf("Case %d: %d ",cs++,tag); else printf("Case %d: -1 ",cs++); } return 0; }