J - Borg maze (minimum spanning tree +bfs)

The question ：
A For aliens , from S set out , Reach every A It's about , Assimilate them , After assimilation A（ Can be split into many ） Can assimilate other A, How many steps does it take to assimilate all aliens （ Only up, down, left and right ）,

Ideas ：
use dfs Take every one. A or S The distance to other aliens is found , Then there is the problem of the shortest path

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N=505;
int MAX=0x3f3f3f3f;
int n,m,k;
char b[N][N],s1[N];
int map[N][N];
int biao[N][N];
int pre[N*N];
int dx[5]={
    1,0,0,-1};// Four directions of traversal  
int dy[5]={
    0,1,-1,0};
struct node{
    
	int u,v,w;
}a[N*(N-1)/2];
struct haha{
    
	int x,y;
	int step;// They count  
}now,next;
int cmp(node x,node y)
{
    
	return x.w<y.w;
}
int find(int x)
{
    
	if(pre[x]==x)
	return x;
	else
	return pre[x]=find(pre[x]);
}
int judge(int u,int v)
{
    
	int fx=find(u);
	int fy=find(v);
	if(fx!=fy)
	{
    
		pre[fy]=fx;
		return 1;
	}
	return 0;
}
void bfs(int x,int y,int ans)
{
    
	memset(biao,0,sizeof(biao));
	queue<haha>Q;
	now.x=x;
	now.y=y;
	now.step=0;
	biao[x][y]=1;
	Q.push(now);// Join the queue  
	while(!Q.empty())
	{
    
		now=Q.front();
		Q.pop();
		for(int i=0;i<4;i++)
		{
    
			next.x=now.x+dx[i];
			next.y=now.y+dy[i];// I feel like my brain is not working well ,now.y, It was written now.x, Speechless  
			next.step=now.step+1;
			int x1,y1;
			x1=next.x,y1=next.y;
			if(x1>=0&&y1>=0&&x1<n&&y1<m&&biao[x1][y1]==0&&map[x1][y1]!=-1)
			{
    
				biao[x1][y1]=1;
				Q.push(next);
				if(map[x1][y1]>0)
				{
    
					a[k].u=ans;
				    a[k].v=map[x1][y1];
				    a[k++].w=next.step;
				}
				
			}
		 } 
	}
}
int main()
{
    
   int t;
	cin>>t;
	while(t--)
	{
    
		 int num=1;
        scanf("%d%d",&m,&n);
        memset(map,0,sizeof(map));
        gets(b[0]);// Clear spaces  
        //getchar();// Out-of-service , because m,n There may be a lot of spaces after  
        for(int i=0;i<n;i++)
        {
    
           gets(b[i]);// The input string with spaces cannot be used scanf, 
           
        }
        for(int i=0; i<n; i++)
        {
    
            for(int j=0; j<m; j++)
            {
    
                if(b[i][j]==' ')
                    map[i][j]=0;
                if(b[i][j]=='#')
                    map[i][j]=-1;
                if(b[i][j]=='A'||b[i][j]=='S')
                {
    
                    map[i][j]=num;
                    num++;// Statistics A,S The number of  
                }
            }
        }
		k=0;// Used to calculate the number of paths  
		for(int i=0;i<n;i++)
		{
    
			for(int j=0;j<m;j++)
			{
    
				if(map[i][j]>0)
				bfs(i,j,map[i][j]);
			}
		}
		for(int i=0;i<=num;i++)//kruskal Algorithm  
		pre[i]=i;
		sort(a,a+k,cmp);
		int sum=0;
		for(int i=0;i<k;i++)
		{
    
		  if(judge(a[i].u,a[i].v))
		  {
    
		  	sum+=a[i].w;
		  }
		} 
		//cout<<sum<<endl;
		printf("%d\n",sum);
	}
   return 0;
}