CodeM2018 初赛A轮 D 迷宫

题目链接https://www.nowcoder.com/acm/contest/150/D

题意:略。

思路:考虑暴力的话无非对每个关键点作BFS然后连边跑最小生成树算法,需要优化。然后感觉这是一个套路,即把所有的关键点加入队列进行BFS,这样跑一遍BFS即可知道其他非关键点到它最近的关键点的距离,在BFS的时候,如果当前节点扩展到的下一个节点已经被访问过,我们设当前节点距离最近的关键点是a,另一个是b,那么只要ab不同,我们就把ab连一条两个节点距离之和再加一边权的边,这样即可优化建边,且搜索一遍的时间复杂度是O(nm),这样做的正确性是,考虑一条边,如果其中一个端点在被a访问到以后又被c访问到,即存在cb的最短路径经过这条边,我们完全不需要加入,因为这样你加入的边长一定是不优于a->b的边的,大概是这样(雾),自己还没有完全想清楚,先记住这么个套路好了。

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2000*2000+10;
struct Edge{
    int u,v,val;
    bool operator<(const Edge&rhs)const{
        return val<rhs.val;
    }
};
int n,m,i,j,k,x,y,fa[N];
int pre[2005][2005],dis[2005][2005];
char col[2005][2005],row[2005][2005];
vector<Edge>edges;
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
queue<pair<int,int> >Q;
void work(int x,int y,int id,int len){
    if (pre[x][y]==id) return;
    if (!pre[x][y]){
        pre[x][y]=id;
        dis[x][y]=len;
        Q.push(MP(x,y));
        return;
    }
    edges.PB((Edge){pre[x][y],id,dis[x][y]+len});
}
int main(){
    read(n),read(m),read(k);
    for (i=1;i<=n;i++) scanf("%s",col[i]+1);
    for (i=1;i<n;i++) scanf("%s",row[i]+1);
    for (i=1;i<=k;i++){
        read(x),read(y);
        Q.push(MP(x,y));
        pre[x][y]=i;
        fa[i]=i;
    }
    while (!Q.empty()){
        auto cur=Q.front();Q.pop();
        x=cur.first,y=cur.second;
        if (x!=n&&row[x][y]!='1') work(x+1,y,pre[x][y],dis[x][y]+1);
        if (x!=1&&row[x-1][y]!='1') work(x-1,y,pre[x][y],dis[x][y]+1);
        if (y!=m&&col[x][y]!='1') work(x,y+1,pre[x][y],dis[x][y]+1);
        if (y!=1&&col[x][y-1]!='1') work(x,y-1,pre[x][y],dis[x][y]+1);
    }
    sort(edges.begin(),edges.end());
    int sum=0,cnt=0;
    for (i=0;i<(int)edges.size();i++){
        int u=edges[i].u,v=edges[i].v,w=edges[i].val;
        u=Find(u),v=Find(v);
        if (u^v){
            sum+=w;
            fa[u]=v;
            if (++cnt>=k-1) break;
        }
    }
    printf("%d\n",sum);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注