#include#include #include #include #include #include using namespace std;const int INF=10e8;const int MAXN=55;int col,row,k,minn;char str[MAXN][MAXN];int maze[MAXN][MAXN],dist[MAXN*2][MAXN*2],lowdis[MAXN*2];int dx[]={-1,0,0,1};int dy[]={ 0,-1,1,0};bool vist[MAXN][MAXN]; //BFS时记录是否走过bool vis[MAXN*2];struct Node{ int x,y; int dis;}node[MAXN*2];bool judge(int x,int y){ //判断是否过界，或者是否能继续查下去 if(x<0||x>=row||y<0||y>=col||maze[x][y]==-1||vist[x][y]==1) return false; return true;}void BFS(int n)//用bfs建立邻接矩阵{ queue que; //que为Node型的队列变量 memset(dist,0,sizeof(dist)); Node u,next; //u用来保存当前的队列元素，next保存下一个队列元素 for(int i=1;i<=n;i++) { while(!que.empty()) que.pop(); //清空队列元素 memset(vist,0,sizeof(vist)); int tot=0; node[i].dis=0; vist[node[i].x][node[i].y]=1; que.push(node[i]); while(!que.empty()) { u=que.front();que.pop(); int x=u.x,y=u.y; if(maze[x][y]!=0&&maze[x][y]!=-1) { tot++; dist[i][maze[x][y]]=dist[maze[x][y]][i]=u.dis; if(tot==n) break; } for(int j=0;j<4;j++) //从u点的四个方向上查找 { int xx=u.x+dx[j],yy=u.y+dy[j]; if(judge(xx,yy)) { next.x=xx;next.y=yy; next.dis=u.dis+1; vist[xx][yy]=1; que.push(next); } } } }}int Prim(int n){ int ans=0; memset(vis,0,sizeof(vis)); vis[1]=1; for(int i=1;i<=n;i++) lowdis[i]=dist[1][i]; for(int i=1;i<=n-1;i++) { minn=INF;k=-1; for(int j=1;j<=n;j++) { if(!vis[j]&&minn>lowdis[j]) { minn=lowdis[j]; k=j; } } if(k==-1) break; ans+=minn;vis[k]=1; for(int j=1;j<=n;j++) if(!vis[j]&&lowdis[j]>dist[k][j]) lowdis[j]=dist[k][j]; } return ans;}int main(){ int n; scanf("%d",&n); while(n--) { int cnt=0; memset(node,0,sizeof(node)); scanf("%d%d",&col,&row); char ch[MAXN]; gets(ch);//重点！处理输入时多余的空格 for(int i=0;i