POJ - 3026 Borg Maze（最小生成树）

题意

在一个y行 x列的迷宫中，有可行走的通路空格’ ‘，不可行走的墙’#’，还有两种英文字母A和S，现在从S出发，要求用最短的路径L连接所有字母，输出这条路径L的总长度。

分析

注意审题！！一开始读成可在任意位置分头走，结果题意限制了只能在字母处分开。这样就好做多了，L就是最小生成树的权值。因为这和生成树的处理过程很像，每一次找最近的点加入到集合中，即走过的路不用再考虑。本题难度在建图，先找出那几个字母的位置，给他们标号，然后逐个字母点进行bfs，找出他们到其他字母点的最短距离。建好后就套一下最小生成树的模板。坑点：最小树上的顶点数最多为100而不是50，用gets接受一行字符串，使用getchar()接受多余字符会wa（不知道原因），但在scanf中加多个空格就可以。。。

#include<iostream>

#include<cmath>

#include<cstring>

#include<queue>

#include<vector>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#define rep(i,e) for(int i=0;i<(e);i++)

#define rep1(i,e) for(int i=1;i<=(e);i++)

#define repx(i,x,e) for(int i=(x);i<=(e);i++)

#define X first

#define Y second

#define PB push_back

#define MP make_pair

#define mset(var,val) memset(var,val,sizeof(var))

#define scd(a) scanf("%d",&a)

#define scdd(a,b) scanf("%d%d",&a,&b)

#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define pd(a) printf("%d\n",a)

#define scl(a) scanf("%lld",&a)

#define scll(a,b) scanf("%lld%lld",&a,&b)

#define sclll(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)

#define IOS ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

typedef long long ll;

template <class T>

void test(T a){cout<<a<<endl;}

template <class T,class T2>

void test(T a,T2 b){cout<<a<<" "<<b<<endl;}

template <class T,class T2,class T3>

void test(T a,T2 b,T3 c){cout<<a<<" "<<b<<" "<<c<<endl;}

template <class T>

inline bool scan_d(T &ret){

    char c;int sgn;

    if(c=getchar(),c==EOF) return ;

    while(c!='-'&&(c<''||c>'')) c=getchar();

    sgn=(c=='-')?-:;

    ret=(c=='-')?:(c-'');

    while(c=getchar(),c>=''&&c<='') ret = ret*+(c-'');

    ret*=sgn;

    return ;

}

//const int N = 1e6+10;

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3fll;

const ll mod = ;

int T;

void testcase(){

    printf("Case %d:",++T);

}

const int MAXN =  ;

const int MAXM = ;

const double eps = 1e-;

const double PI = acos(-1.0);

bool vis[MAXM];

int lowc[MAXM];

int cost[MAXM][MAXM],index[MAXM][MAXM];

char maze[MAXM][MAXM];

int x,y;

struct node{

    int x,y,step;

};

bool vist[MAXM][MAXM];

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

bool check(int a,int b){

    if(a<||a>=y) return false;

    if(b<||b>=x) return false;

    if(maze[a][b]=='#') return false;

    return true;

}

void bfs(int s,int x,int y){

    mset(vist,false);

    vist[x][y]=true;

    node now,tmp;

    now.x=x;now.y=y;now.step=;

    queue<node> que;

    que.push(now);

    while(!que.empty()){

        now = que.front();

        que.pop();

        if(index[now.x][now.y]!=-){

            cost[s][index[now.x][now.y]]=now.step;

//            cost[index[now.x][now.y]][s]=now.step;

        }

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

            tmp.x = now.x+dir[i][];

            tmp.y = now.y+dir[i][];

            tmp.step = now.step+;

            if(!vist[tmp.x][tmp.y]&&check(tmp.x,tmp.y)){

                vist[tmp.x][tmp.y]=true;

                que.push(tmp);

            }

        }

    }

}

int Prim(int n){

    int ans=;

    mset(vis,false);

    vis[]=true;

    for(int i=;i<n;i++) lowc[i]=cost[][i];

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

        int minc = inf;

        int p = -;

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

            if(!vis[j]&&minc>lowc[j]){

                minc = lowc[j];

                p = j;

            }

        }

        if(minc == inf){

            return -;

        }

        ans+=minc;

        vis[p]=true;

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

            if(!vis[j]&&lowc[j]>cost[p][j]){

                lowc[j] = cost[p][j];

            }

        }

    }

    return ans;

}

int main() {

#ifdef LOCAL

    freopen("data.in","r",stdin);

#endif // LOCAL

    int n;

    scanf("%d",&n);

    while(n--){

        scanf("%d%d ",&x,&y);

        mset(index,-);

        for(int i=;i<MAXM;i++) cost[i][i]=;

        int cnt=;

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

            gets(maze[i]);

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

                if(maze[i][j]=='A'||maze[i][j]=='S'){

                    index[i][j]=cnt++;

                }

            }

        }

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

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

                if(index[i][j]!=-){

                    bfs(index[i][j],i,j);

                }

            }

        }

        int ans=Prim(cnt);

        printf("%d\n",ans);

    }

    return ;

}

秒客网

POJ - 3026 Borg Maze（最小生成树）

相关文章