J - Borg Maze

J - Borg Maze

思路：bfs+最小生成树。

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 110

using namespace std;

int fa[MAXN];

struct nond{

    int x,y,z;

}v[MAXN*MAXN];

struct none{

    int x,y,z;

};

int dx[]={,-,,};

int dy[]={,,,-};

int t,n,m,tot,sum,ans,point;

int map[MAXN][MAXN],vis[MAXN][MAXN];

void bfs(int x,int y){

    queue<none>que;none s;s.x=x;s.y=y;s.z=;

    memset(vis,,sizeof(vis));vis[x][y]=;

    que.push(s);int k=;

    while(!que.empty()){

        none now=que.front();

        que.pop();

        for(int i=;i<;i++){

            int cx=now.x+dx[i];

            int cy=now.y+dy[i];

            int cz=now.z+;

            if(cx>=&&cx<=n&&cy>=&&cy<=m&&map[cx][cy]>=&&!vis[cx][cy]){

                if(map[cx][cy]>){ v[++tot].x=map[x][y];v[tot].y=map[cx][cy];v[tot].z=cz;k++; }

                if(k==point)    return ;

                none tmm;tmm.x=cx;tmm.y=cy;tmm.z=cz;

                vis[cx][cy]=;que.push(tmm);

            }

        }

    }

}

int cmp(nond a,nond b){

    return a.z<b.z;

}

int find(int x){

    if(fa[x]==x)    return x;

    else return fa[x]=find(fa[x]);

}

int main(){

    scanf("%d",&t);

    char tmp[MAXN];

    while(t--){

        scanf("%d%d",&m,&n);

        gets(tmp);

        for(int i=;i<=n;i++){

            for(int j=;j<=m;j++){

                char x;scanf("%c",&x);

                if(x=='#') map[i][j]=-;

                else if(x==' ')    map[i][j]=;

                else map[i][j]=++point;

            }

            char c;scanf("%c",&c);

        }

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++)

                if(map[i][j]>)    bfs(i,j);

        sort(v+,v++tot,cmp);

        for(int i=;i<=point;i++)    fa[i]=i;

        for(int i=;i<=tot;i++){

            int dx=find(v[i].x);

            int dy=find(v[i].y);

            if(dx==dy)    continue;

            fa[dy]=dx;sum++;

            ans+=v[i].z;

            if(sum==point-)    break;

        }

        cout<<ans<<endl;

        ans=;tot=;sum=;point=;

    }

}