题目链接:https://www.nowcoder.com/acm/contest/150/D
题意:略。
思路:考虑暴力的话无非对每个关键点作BFS然后连边跑最小生成树算法,需要优化。然后感觉这是一个套路,即把所有的关键点加入队列进行BFS,这样跑一遍BFS即可知道其他非关键点到它最近的关键点的距离,在BFS的时候,如果当前节点扩展到的下一个节点已经被访问过,我们设当前节点距离最近的关键点是a,另一个是b,那么只要a与b不同,我们就把a与b连一条两个节点距离之和再加一边权的边,这样即可优化建边,且搜索一遍的时间复杂度是O(nm),这样做的正确性是,考虑一条边,如果其中一个端点在被a访问到以后又被c访问到,即存在c到b的最短路径经过这条边,我们完全不需要加入,因为这样你加入的边长一定是不优于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;
}