Killing Aliens in Borg Maze

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF (1<<29)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define IN(n) int n;scanf("%d",&n);
#define FOR(i, m, n) for (int i(m); i < n; i++)
#define REP(i, n) FOR(i, 0, n)
#define F(n) REP(i, n)
#define FF(n) REP(j, n)
#define FT(m, n) FOR(k, m, n)
#define aa first
#define bb second
void ga(int N,int *A){F(N)scanf("%d",A+i);}
#define MX (55)
#define GL(S) fgets(S,MX,stdin)
#define in(X,Y) (~X&&~Y&&X<N&&Y<M)
char s[MX][MX];
int N,M,L,E,sx[]={1,-1,0,0},sy[]={0,0,-1,1},A[MX][MX];
struct nd{
   int a,b,w,is;
   bool operator<(const nd&r)const{return w<r.w;}
}g[1<<14];
int C[128];
int geco(int a){
    return C[a]=(a==C[a]?a:geco(C[a]));
}
bool con(int a,int b){
    if(geco(a)==geco(b))return 0;
    return C[C[b]]=C[a],1;
}
ll spa(int N,int M){
    ll S(0);
    sort(g,g+M);
    iota(C,C+N,0);
    F(M)if(con(g[i].a,g[i].b))S+=g[i].w,g[i].is=1;
    return S;
}
int qx[2500],qy[2500],qp[2500],cn[MX][MX];
void bfs(int x,int y,int l){
    int b(-1),e(1),tx,ty,p;
    CL(cn,-1),cn[*qx=x][*qy=y]=0;
    while(++b<e){
        x=qx[b],y=qy[b],p=qp[b]+1;
        F(4){
            tx=x+sx[i],ty=y+sy[i];
            if(!in(tx,ty)||~cn[tx][ty]||s[tx][ty]==35)continue;
            if(A[tx][ty])g[E++]={l-1,A[tx][ty]-1,p,0};
            cn[tx][ty]=qp[e]=p,qx[e]=tx,qy[e++]=ty;
        }
    }
}
int main(void){
    IN(tt)F(tt){
        CL(A,E=L=0);
        scanf("%d%d",&M,&N),GL(*s);
        F(N)GL(s[i]);
        F(N)FF(M)if(isupper(s[i][j]))A[i][j]=++L;
        F(N)FF(M)if(A[i][j])bfs(i,j,A[i][j]);
        printf("%d\n",(int)spa(L,E));
    }
    return 0;
}