Hướng dẫn cho Miền hai màu (C.P.VNOI 2021 LMH R3)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho một bảng kích thước \(m \times n\), mỗi ô \((i, j)\) có một mã màu \(a_{ij}\). Một "miền" là một tập hợp các ô liên thông với nhau (có thể di chuyển giữa hai ô bất kỳ trong miền qua các cạnh chung). Tìm miền có số lượng ô lớn nhất sao cho trong miền đó chỉ chứa tối đa 2 loại mã màu khác nhau.

Phân tích

Điều kiện: \(m, n \leq 1000\), \(a_{ij} \leq 10^6\). Số lượng ô tối đa là \(10^6\).
Nhận xét 1: Một miền gồm tối đa 2 màu \((C_1, C_2)\) sẽ là tập hợp các thành phần liên thông của các ô có màu \(C_1\) và các ô có màu \(C_2\) nằm kề cạnh nhau.
Nhận xét 2: Trước hết, ta có thể gộp các ô cùng màu nằm kề nhau thành các "siêu đỉnh". Mỗi siêu đỉnh này đại diện cho một thành phần liên thông gồm các ô cùng màu. Kích thước của siêu đỉnh là số lượng ô trong thành phần liên thông đó.
Nhận xét 3: Bài toán trở thành: Tìm hai màu \(C_1\) và \(C_2\) sao cho khi nối tất cả các thành phần liên thông của màu \(C_1\) và \(C_2\) có cạnh kề nhau, ta được một miền có tổng số ô lớn nhất.

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt qua tất cả các cặp màu \((C_1, C_2)\) xuất hiện trong bảng. Với mỗi cặp màu, ta sử dụng thuật toán tìm kiếm theo chiều rộng (BFS) hoặc chiều sâu (DFS) để tìm miền liên thông lớn nhất chỉ chứa hai màu này.

Độ phức tạp

Thời gian: Gọi \(K\) là số lượng màu khác nhau. Số cặp màu là \(O(K^2)\). Mỗi lần kiểm tra mất \(O(m \times n)\). Tổng độ phức tạp \(O(K^2 \cdot m \cdot n)\).
Đánh giá: Với \(K\) có thể lên tới \(10^6\), cách này không khả thi.

Code Brute Force

C++

#include <bits/stdc++.h>
using namespace std;

int m, n;
int a[1000][1000];
bool visited[1000][1000];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int bfs(int r, int c, int c1, int c2) {
    queue<pair<int, int>> q;
    q.push({r, c});
    visited[r][c] = true;
    int count = 0;
    while (!q.empty()) {
        pair<int, int> curr = q.front(); q.pop();
        count++;
        for (int i = 0; i < 4; i++) {
            int nx = curr.first + dx[i];
            int ny = curr.second + dy[i];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                if (a[nx][ny] == c1 || a[nx][ny] == c2) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
    }
    return count;
}

int main() {
    cin >> m >> n;
    set<int> colors;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            colors.add(a[i][j]);
        }
    }
    vector<int> col_list(colors.begin(), colors.end());
    int ans = 0;
    for (int i = 0; i < col_list.size(); i++) {
        for (int j = i; j < col_list.size(); j++) {
            memset(visited, 0, sizeof(visited));
            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    if (!visited[r][c] && (a[r][c] == col_list[i] || a[r][c] == col_list[j])) {
                        ans = max(ans, bfs(r, c, col_list[i], col_list[j]));
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}

Python

import sys
sys.setrecursionlimit(2000)

def solve():
    m, n = map(int, sys.stdin.readline().split())
    a = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

    colors = set()
    for row in a:
        for val in row:
            colors.add(val)

    col_list = list(colors)
    ans = 0

    for i in range(len(col_list)):
        for j in range(i, len(col_list)):
            c1, c2 = col_list[i], col_list[j]
            visited = [[False for _ in range(n)] for _ in range(m)]
            for r in range(m):
                for c in range(n):
                    if not visited[r][c] and (a[r][c] == c1 or a[r][c] == c2):
                        # BFS/DFS logic here
                        count = 0
                        stack = [(r, c)]
                        visited[r][c] = True
                        while stack:
                            curr_r, curr_c = stack.pop()
                            count += 1
                            for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
                                nr, nc = curr_r + dr, curr_c + dc
                                if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
                                    if a[nr][nc] == c1 or a[nr][nc] == c2:
                                        visited[nr][nc] = True
                                        stack.append((nr, nc))
                        ans = max(ans, count)
    print(ans)

Hướng giải quyết (Tối ưu)

Ý tưởng

Sử dụng cấu trúc dữ liệu Disjoint Set Union (DSU) để quản lý các miền liên thông. Quá trình gồm 2 giai đoạn:

Giai đoạn 1: Gom nhóm các ô cùng màu.
- Duyệt qua tất cả các cạnh kề nhau trong bảng. Nếu hai ô kề nhau có cùng màu, ta thực hiện Union chúng lại.
- Sau bước này, mỗi thành phần liên thông (miền đơn sắc) sẽ có một đại diện trong DSU và kích thước tương ứng.
Giai đoạn 2: Xét các cặp màu kề nhau.
- Liệt kê tất cả các cạnh nối giữa hai ô có màu khác nhau \((C_1, C_2)\).
- Sắp xếp các cạnh này theo cặp màu \((C_1, C_2)\) để xử lý các cạnh của cùng một cặp màu liên tiếp nhau.
- Với mỗi cặp màu \((C_1, C_2)\):
  - Thực hiện Union các thành phần liên thông (đã gom ở Giai đoạn 1) mà có cạnh nối giữa chúng.
  - Cập nhật kết quả cực đại từ kích thước các miền mới tạo ra.
  - Quan trọng: Sau khi xử lý xong một cặp màu, ta phải hoàn tác (rollback) các thao tác Union để trả DSU về trạng thái ban đầu của Giai đoạn 1, chuẩn bị cho cặp màu tiếp theo.

Chi tiết cài đặt

Để tiết kiệm bộ nhớ và thời gian, ta mã hóa cặp màu \((C_1, C_2)\) thành một số duy nhất (ví dụ: \(min(C_1, C_2) \times 10^6 + max(C_1, C_2)\)).
Việc hoàn tác trong DSU có thể thực hiện đơn giản bằng cách lưu lại các giá trị lab trước khi thay đổi, hoặc trong bài này, vì ta chỉ Union các đại diện nhóm từ Giai đoạn 1, ta chỉ cần gán lại giá trị lab gốc sau mỗi cặp màu.

Độ phức tạp

Thời gian: \(O(M \cdot N \log(M \cdot N))\) do bước sắp xếp các cạnh giữa các màu khác nhau. Các thao tác DSU gần như là hằng số.
Bộ nhớ: \(O(M \cdot N)\) để lưu bảng và cấu trúc DSU.

Code tham khảo

C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
const long long MAXC = 1000001;

int m, n;
int a[MAXN][MAXN];
int lab[MAXN * MAXN], savelab[MAXN * MAXN];
int res = 1;

struct Edge {
    int u, v;
    long long code;
};

int encode(int x, int y) { return x * n + y; }

long long get_pair_code(int c1, int c2) {
    if (c1 > c2) swap(c1, c2);
    return c1 * MAXC + c2;
}

int find_set(int u) {
    return lab[u] < 0 ? u : lab[u] = find_set(lab[u]);
}

int find_set_no_path(int u) { // Dùng khi cần rollback
    return lab[u] < 0 ? u : find_set_no_path(lab[u]);
}

void join(int r, int s) {
    if (r == s) return;
    if (lab[s] < lab[r]) swap(r, s);
    lab[r] += lab[s];
    lab[s] = r;
    res = max(res, -lab[r]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> m >> n)) return 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    vector<Edge> edges;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i + 1 < m) edges.push_back({encode(i, j), encode(i + 1, j), get_pair_code(a[i][j], a[i + 1][j])});
            if (j + 1 < n) edges.push_back({encode(i, j), encode(i, j + 1), get_pair_code(a[i][j], a[i][j + 1])});
        }
    }

    fill(lab, lab + m * n, -1);
    // Giai đoạn 1: Nối các ô cùng màu
    for (auto &e : edges) {
        if (e.code / MAXC == e.code % MAXC) {
            int r = find_set(e.u), s = find_set(e.v);
            if (r != s) join(r, s);
        }
    }

    // Lưu trạng thái sau giai đoạn 1 và cập nhật đỉnh cạnh
    for (int i = 0; i < m * n; i++) {
        find_set(i); // Path compression
        savelab[i] = lab[i];
    }
    for (auto &e : edges) {
        e.u = find_set(e.u);
        e.v = find_set(e.v);
    }

    // Giai đoạn 2: Xét các cặp màu khác nhau
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
        return a.code < b.code;
    });

    int i = 0;
    while (i < edges.size()) {
        if (edges[i].code / MAXC == edges[i].code % MAXC) {
            i++; continue;
        }
        int j = i;
        while (j < edges.size() && edges[j].code == edges[i].code) {
            int r = find_set_no_path(edges[j].u), s = find_set_no_path(edges[j].v);
            if (r != s) join(r, s);
            j++;
        }
        // Rollback
        for (int k = i; k < j; k++) {
            lab[edges[k].u] = savelab[edges[k].u];
            lab[edges[k].v] = savelab[edges[k].v];
        }
        i = j;
    }

    cout << res;
    return 0;
}

Python

import sys

# Tăng giới hạn đệ quy cho DSU find_set
sys.setrecursionlimit(2000000)

def solve():
    input_data = sys.stdin.read().split()
    if not input_data: return
    m = int(input_data[0])
    n = int(input_data[1])
    a = []
    idx = 2
    for i in range(m):
        a.append(list(map(int, input_data[idx:idx+n])))
        idx += n

    lab = [-1] * (m * n)

    def find_set(u):
        if lab[u] < 0: return u
        lab[u] = find_set(lab[u])
        return lab[u]

    def find_set_no_path(u):
        curr = u
        while lab[curr] >= 0:
            curr = lab[curr]
        return curr

    res = 1
    def union(r, s):
        nonlocal res
        if r == s: return
        if lab[s] < lab[r]: r, s = s, r
        lab[r] += lab[s]
        lab[s] = r
        if -lab[r] > res: res = -lab[r]

    edges = []
    MAXC = 1000001
    for r in range(m):
        for c in range(n):
            u = r * n + c
            if r + 1 < m:
                v = (r + 1) * n + c
                c1, c2 = a[r][c], a[r+1][c]
                if c1 > c2: c1, c2 = c2, c1
                edges.append([u, v, c1 * MAXC + c2])
            if c + 1 < n:
                v = r * n + (c + 1)
                c1, c2 = a[r][c], a[r][c+1]
                if c1 > c2: c1, c2 = c2, c1
                edges.append([u, v, c1 * MAXC + c2])

    # Giai đoạn 1
    for e in edges:
        if e[2] // MAXC == e[2] % MAXC:
            root_u, root_v = find_set(e[0]), find_set(e[1])
            union(root_u, root_v)

    savelab = list(lab)
    for e in edges:
        e[0] = find_set(e[0])
        e[1] = find_set(e[1])

    edges.sort(key=lambda x: x[2])

    i = 0
    while i < len(edges):
        code = edges[i][2]
        if code // MAXC == code % MAXC:
            i += 1
            continue

        j = i
        changed_nodes = []
        while j < len(edges) and edges[j][2] == code:
            u, v = edges[j][0], edges[j][1]
            root_u, root_v = find_set_no_path(u), find_set_no_path(v)
            if root_u != root_v:
                union(root_u, root_v)
                changed_nodes.append(root_u)
                changed_nodes.append(root_v)
            j += 1

        # Rollback
        for node in changed_nodes:
            lab[node] = savelab[node]
        i = j

    print(res)

solve()

Bình luận

Tải bình luận...

Không có bình luận nào.