题目链接：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;
}