#include<iostream>#include<stdio.h>#include<string.h>#include<math.h>#include<algorithm>#include<vector>#include<string>#include<map>#include<queue>#include<set>using namespace std;int T,n,m,cnt;char maze[310][310];bool vis[310][310];int dist[310][310];int mincost[310];bool used[310];int dx[]={-1,1,0,0};int dy[]={0,0,-1,1};struct Point{ int x,y,cnt,dist,flag;}point[310];void bfs(int d){ memset(vis,0,sizeof(vis)); queue<Point> q; q.push(point[d]); vis[point[d].y][point[d].x]=true; while(!q.empty()) { Point p=q.front(); q.pop(); if(p.flag) dist[d][p.cnt]=dist[p.cnt][d]=p.dist; for(int i=0;i<4;i++) { Point pnew={p.x+dx[i],p.y+dy[i],0,p.dist+1,0}; if(0<=pnew.y&&pnew.y<m&&0<=pnew.x&&pnew.x<n&&maze[pnew.y][pnew.x]!='#'&&!vis[pnew.y][pnew.x]) { if(maze[pnew.y][pnew.x]!=' ') { for(int j=0;j<cnt;j++) if(point[j].x==pnew.x&&point[j].y==pnew.y) { pnew.cnt=point[j].cnt; break; } pnew.flag=1; } q.push(pnew); vis[pnew.y][pnew.x]=true; } } }}int main(){ scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); char ssss[100];gets(ssss); cnt=0; memset(dist,0,sizeof(dist)); memset(maze,0,sizeof(maze)); memset(point,0,sizeof(point)); for(int i=0;i<m;i++) { gets(maze[i]); for(int j=0;j<n;j++) { if(maze[i][j]=='S'||maze[i][j]=='A') { point[cnt].flag=1; point[cnt].y=i; point[cnt].x=j; point[cnt].dist=0; point[cnt].cnt=cnt; cnt++; } } } for(int i=0;i<cnt;i++) bfs(i); for(int i=0;i<cnt;i++) { mincost[i]=1000000000; used[i]=false; } int res=0; mincost[0]=0; while(1) { int v=-1; for(int u=0;u<cnt;u++) if(!used[u]&&(mincost[u]<mincost[v]||v==-1)) v=u; if(v==-1) break; used[v]=true; res+=mincost[v]; for(int u=0;u<cnt;u++) mincost[u]=min(mincost[u],dist[v][u]); } printf("%dn",res); } return 0;}
