Code mẫu

#include <bits/stdc++.h>

using namespace std;
const string filename = "QPATH";

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

int n, m;
vector< vector<int> > a;
int q;
int x1, y1, x2, y2;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0 , -1};

int par[100001];

int anc(int x)
{
    if (par[x] == x) return x;
    return par[x] = anc(par[x]);
}

void join(int x, int y)
{
    par[anc(x)] = anc(y);
}

int id(int row, int col)
{
    return (row - 1) * m + col; 
}

int h[100001];
int mn_val[100001][21], pt[100001][21];
vector<ii> adj[100001];

void dfs(int u, int p) 
{
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i].first, val = adj[u][i].second;
        if (v == p) continue;
        h[v] = h[u] + 1;
        dfs(v, u);
        mn_val[v][0] = val;
        pt[v][0] = u;
    }
}

int cal(int u, int v)
{
    if (h[u] > h[v])
        swap(u, v);
    int ans = 1e9;
    for (int j = 20; j >= 0; j--)
        if (h[pt[v][j]] >= h[u]) {
            ans = min(ans, mn_val[v][j]);
            v = pt[v][j];
        }   
    if (u == v)
        return ans;
    for (int j = 20; j >= 0; j--)
        if (pt[u][j] != pt[v][j]) {
            ans = min(ans, mn_val[u][j]);
            ans = min(ans, mn_val[v][j]);
            u = pt[u][j];
            v = pt[v][j];
        }
    ans = min(ans, mn_val[u][0]);   
    ans = min(ans, mn_val[v][0]);
    return ans;
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen( (filename + ".inp").c_str(), "r", stdin);
    freopen( (filename + ".out").c_str(), "w", stdout);

    cin >> n >> m;
    a.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i].resize(m + 1);
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    }

    vector<iii> E;
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= m; y++)
            for (int k = 0; k < 4; k++) {
                int xx = x + dx[k];
                int yy = y + dy[k];
                if (1 <= xx && xx <= n && 1 <= yy && yy <= m) {
                    E.push_back(iii(min(a[x][y], a[xx][yy]), ii(id(x, y), id(xx, yy))));
                }
            }

    sort (E.begin(), E.end(), greater<iii>());
    for (int i = 1; i <= n * m; i++)
        par[i] = i;
    for (int i = 0; i < E.size(); i++) {
        int val = E[i].first, u = E[i].second.first, v = E[i].second.second;
        if (anc(u) != anc(v)) {
            join(u, v);
            adj[u].push_back(ii(v, val));
            adj[v].push_back(ii(u, val));
        }                
    }

    h[1] = 1;
    dfs(1, -1);
    for (int j = 1; j <= 20; j++)
        for (int i = 1; i <= n * m; i++) {
            pt[i][j] = pt[pt[i][j - 1]][j - 1];
            mn_val[i][j] = min(mn_val[i][j - 1], mn_val[pt[i][j - 1]][j - 1]);
        }

    cin >> q;
    while (q--) {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << cal(id(x1, y1), id(x2, y2)) << '\n';
    }
}