#include<iostream> #include<stdio.h> #include<cstring> #include<queue> using namespace std; typedef pair<int,int>PII; //原地图 char g[100][100]; int n,m; //存原点和s的坐标 int pos[100][100]; int move[][2]={{1,0},{-1,0},{0,1},{0,-1}}; int cost[110][110]; //距离 int t[100][100]; //处理每个点到其他点的最小距离 void bfs(int sx,int sy) { queue<PII>q; while(!q.empty()) q.pop(); memset(t,-1,sizeof(t)); t[sx][sy]=0; q.push({sx,sy}); while(!q.empty()) { pair<int,int>now=q.front(); q.pop(); if(pos[now.first][now.second]!=-1) //记录(sx,sy)到now的花费 cost[pos[sx][sy]][pos[now.first][now.second]]=t[now.first][now.second]; for(int i=0;i<4;i++) { int tx=now.first+move[i][0]; int ty=now.second+move[i][1]; if(g[tx][ty]=='#'||t[tx][ty]!=-1) continue; t[tx][ty]=t[now.first][now.second]+1; q.push({tx,ty}); } } } const int INF=0x3f3f3f3f; bool vis[110]; int low_cost[110]; //求最小生成树 int Prim(int n) { int ans=0; memset(vis,false,sizeof(vis)); vis[0]=true; for(int i=1;i<n;i++) low_cost[i]=cost[0][i]; for(int i=1;i<n;i++) { int minc=INF; int p=-1; for(int j=0;j<n;j++) if(!vis[j]&&minc>low_cost[j]) { minc=low_cost[j]; p=j; } if(minc==INF) return -1; ans+=minc; vis[p]=true; for(int j=0;j<n;j++) if(!vis[j]&&low_cost[j]>cost[p][j]) low_cost[j]=cost[p][j]; } return ans; } int main() { int t; cin>>t; while(t--) { cin>>m>>n; cin>>g[0]; memset(pos,-1,sizeof pos); int tot=0; for(int i=0;i<n;i++) { gets(g[i]); for(int j=0;j<m;j++) if(g[i][j]=='A'||g[i][j]=='S') pos[i][j]=tot++; } for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(pos[i][j]!=-1) bfs(i,j); printf("%d ",Prim(tot)); } return 0; }