思路：bfs。注意初始化啊，忘了清空vector,TLE一个下午。
代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<cstring> using namespace std; #define ll long long #define pb push_back const int N=15; const int INF=0x3f3f3f3f; char mp[N][N]; bool vis[N][N]; int n,m; int dir[4][2]={1,0,0,1,-1,0,0,-1}; struct Node { int x,y; int step; }; vector<Node>a; int bfs(Node a,Node b,int c) { a.step=0; b.step=0; queue<Node>q; q.push(a); q.push(b); vis[a.x][a.y]=true; vis[b.x][b.y]=true; Node now,next; int ans=0,cnt=2; while(!q.empty()) { now=q.front(); q.pop(); ans=now.step; for(int i=0;i<4;i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; if(0<=next.x&&next.x<n&&0<=next.y&&next.y<m&&mp[next.x][next.y]=='#'&&!vis[next.x][next.y]) { next.step=now.step+1; q.push(next); vis[next.x][next.y]=true; cnt++; } } } if(cnt!=c)return INF; else return ans; } int main() { int t,Case=0; scanf("%d",&t); while(t--) { a.clear(); Case++; int ans=INF; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { scanf("%s",mp[i]); } int cnt=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) if(mp[i][j]=='#') { Node t; t.x=i; t.y=j; a.pb(t); cnt++; } } if(cnt<=2) { printf("Case %d: %d ",Case,0); } else { for(int i=0;i<a.size()-1;i++) { for(int j=i+1;j<a.size();j++) { memset(vis,false,sizeof(vis)); ans=min(ans,bfs(a[i],a[j],cnt)); } } if(ans==INF)ans=-1; printf("Case %d: %d ",Case,ans); } } return 0; }