类似的题:
1347：【例4-8】格子游戏 http://ybt.ssoier.cn:8088/problem_show.php?pid=1347
参考文章: https://www.acwing.com/solution/content/189000/

思路:
1.先建立网格边,如下图:

样例:
2 2
1 1 2 1

走一遍 kruskal 算法，把边按边权排序即可。

代码如下:

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int MAXN = 1005;
const int MAXM = MAXN * MAXN;

struct Edge{
    int from,to;
    int weight;
    bool operator < (const Edge& other)const{
        return weight < other.weight;
    }
};

vector<Edge> edges;

int fa[MAXM];

int row,col;

bool inArea(int x,int y){
    return x >= 1 && x <= row && y >= 1 && y <= col;
}

void init(){
    for(int i = 1;i < MAXM;i++){
        fa[i] = i;
    }
}

int find(int x){
    if(x == fa[x]){
        return x;
    }
    return fa[x] = find(fa[x]);
}

int main(){
    cin >> row >> col;

    init();

    for(int i = 1;i <= row;i++){
        for(int j = 1;j <= col;j++){
            int rx = i;
            int ry = j + 1;
            if(inArea(rx,ry)){
                int p = (i - 1) * col + j;
                int pr = (rx - 1) * col + ry;
                edges.push_back({p,pr,2});
            }
            int dx = i + 1;
            int dy = j;
            if(inArea(dx,dy)){
                int p = (i - 1) * col + j;
                int pr = (dx - 1) * col + dy;
                edges.push_back({p,pr,1});
            }
        }
    }
    int x1,y1,x2,y2;
    while(cin >> x1 >> y1 >> x2 >> y2){
        int id1 = (x1 - 1) * col + y1;
        int id2 = (x2 - 1) * col + y2;
        int pid1 = find(id1);
        int pid2 = find(id2);
        if(pid1 != pid2){
            fa[pid1] = pid2;
        }
    }

    sort(edges.begin(),edges.end());

    int ans = 0;
    for(auto edge : edges){
        int f = edge.from;
        int t = edge.to;
        int w = edge.weight;
        int pf = find(f);
        int pt = find(t);
        if(pf != pt){
            fa[pf] = pt;
            ans += w;
        }
    }

    cout << ans << endl;

    return 0;
}