let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

MTWALK - Mountain Walking

solution.md

Bài này có thể sử dụng tìm kiếm nhị phân kết hợp với BFS/DFS, độ phức tạp là \(O(N^2 H\log H)\) với \(H = 110\) là độ cao tối đa.

Phần sau sẽ trình bày cách sử dụng Disjoint Set để làm bài này.

Đầu tiên ta lưu dữ liệu vào một mảng \(A\), \(A[h]\) chứa tọa độ các ô có độ cao là \(h\).

Gọi \(low\) là chiều cao nhỏ hơn trong chiều cao của 2 ô \((1,1)\) và \((N,N)\), và \(high\) là chiều cao lớn hơn. Dễ thấy kết quả phải lớn hơn hoặc bằng \(low-high\) và đi qua các đỉnh có chiều cao ở giữa \(low\) và \(high\) sẽ không làm ảnh hưởng đến kết quả.

Từ nhận xét trên ta thêm tất cả các đỉnh có chiều cao giữa \(low\) và \(high\) vào tập các đỉnh đang xét. Sau đó lần lượt duyệt \(h\) từ \(low\) trở về 0:

Ở mỗi bước ta thêm các đỉnh trong \(A[h]\) vào các đỉnh đang xét, sau đó thử cho \(k\) chạy từ \(high\) trở lên, thêm \(A[k]\) vào các đỉnh đang xét rồi kiểm tra xem có thể đi từ \((1,1)\) đến \((N,N)\) không.

Để làm được thao tác trên ta cần chỉnh sửa cấu trúc Disjoint Set lại một ít. Xem code bên dưới để biết thêm chi tiết.

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;

struct pack { int i, j; };

struct UnionFind {
    int m;
    vector<int> cha, rank;
    UnionFind(int m): m(m), cha(m), rank(m) {
        reset();
    }
    void add(int i, int j, int n) {
        int id = i*n + j;
        if (cha[id] >= 0) return;
        cha[id] = id;
        if (i > 0) join(id, id-n);
        if (j > 0) join(id, id-1);
        if (i < n-1) join(id, id+n);
        if (j < n-1) join(id, id+1);
    }
    void add(const vector<pack> &p, int n) {
        for (auto &p: p) add(p.i, p.j, n);
    }
    bool test(int u, int v) {
        u = find(u);
        v = find(v);
        return u==v && u>=0;
    }

    void reset() {
        cha.assign(m, -1);
        rank.assign(m, 0);
    }
    int find(int u) {
        if (cha[u] < 0) return -1;
        if (cha[u] != u) cha[u] = find(cha[u]);
        return cha[u];
    }
    void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u < 0 || v < 0 || u == v) return;
        if (rank[u] == rank[v]) rank[u]++;
        if (rank[u]<rank[v]) cha[u] = v;
        else cha[v] = u;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    vector<pack> a[111];
    int low_h, high_h, max_h=0;
    int n; cin >> n;
    int m = n*n;
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) {
        int h; cin >> h;
        a[h].push_back({i,j});
        if (i==0 && j==0) low_h = h;
        if (i==n-1 && j==n-1) high_h = h;
        max_h = max(max_h, h);
    }
    if (low_h > high_h) swap(low_h, high_h);

    UnionFind u(m);
    for (int h=low_h; h<=high_h; h++) u.add(a[h], n);

    int res = 111;
    for (int h=low_h; h>=0; h--) {
        u.add(a[h], n);
        UnionFind f(u);
        for (int h1=high_h; h1<=max_h; h1++) {
            f.add(a[h1], n);
            if (f.test(0, m-1)) {
                res = min(res, h1-h);
                break;
            }
        }
    }

    cout << res;
    return 0;
}
Comments