Editorial for Quần Đảo Pixel


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Nghaiz

Lời giải: Quần Đảo Pixel

Chủ đề: tập hợp (set) chứa tuple, vòng lặp while để loang

Tóm tắt đề

Cho \(n\) ô đất (có thể trùng) trên lưới vô hạn, tọa độ tới \(10^9\). Đếm số thành phần liên thông (theo cạnh) và tổng số cạnh tiếp giáp giữa đất và nước.

Bước 1: lưu bản đồ bằng set các tuple

Tọa độ lên tới \(10^9\) nên không thể tạo mảng hai chiều (cần tới \(4 \cdot 10^{18}\) ô). Nhưng chỉ có tối đa \(2 \cdot 10^5\) ô đất, nên ta chỉ cần lưu những ô đất:

dat = set()
for ...:
    dat.add((x, y))

set tự động loại các ô bị chạm nhiều lần, và phép kiểm tra (x, y) in dat chỉ mất \(O(1)\) trung bình. tuple dùng được làm phần tử của set vì nó không thay đổi được (còn list thì không).

Bước 2: đếm bờ biển

Với mỗi ô đất, xét \(4\) ô kề cạnh. Ô kề nào không nằm trong dat thì đó là nước, cạnh chung là một đơn vị bờ biển. Cách đếm này tự động tính cả bờ hồ, vì ô hồ cũng không nằm trong dat.

Bước 3: đếm đảo bằng cách "loang"

Duyệt từng ô đất. Nếu ô này chưa được thăm thì nó thuộc một hòn đảo mới: tăng bộ đếm, rồi loang ra toàn bộ hòn đảo đó và đánh dấu đã thăm:

hang_doi = [o]
while hang_doi:
    x, y = hang_doi.pop()
    for dx, dy in HUONG:
        ke = (x + dx, y + dy)
        if ke in dat and ke not in da_tham:
            da_tham.add(ke)
            hang_doi.append(ke)

Vì sao phải dùng while mà không dùng đệ quy? Một hòn đảo có thể là một đường dài \(2 \cdot 10^5\) ô. Hàm loang đệ quy sẽ lồng sâu \(2 \cdot 10^5\) tầng:

  • với giới hạn mặc định (\(1000\) tầng), Python báo RecursionError → IR;
  • nếu tăng giới hạn bằng sys.setrecursionlimit(10**7) thì kết quả phụ thuộc phiên bản Python của máy chấm: với Python 3.10 trở về trước, ngăn xếp C bị tràn và chương trình sập → RTE; từ Python 3.11 trở đi chương trình có thể vẫn chạy được nhưng tốn rất nhiều bộ nhớ. Đừng đặt cược vào điều đó.

Dùng một list làm "ngăn xếp tự quản lý" như trên thì không bao giờ gặp vấn đề này.

Độ phức tạp

Mỗi ô đất được xét \(O(1)\) lần, mỗi lần kiểm tra \(4\) ô kề: tổng \(O(n)\).

Code mẫu

import sys

HUONG = ((1, 0), (-1, 0), (0, 1), (0, -1))


def doc_ban_do():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    dat = set()
    for i in range(n):
        dat.add((int(data[1 + 2 * i]), int(data[2 + 2 * i])))
    return dat


def dem_bo_bien(dat):
    bo_bien = 0
    for x, y in dat:
        for dx, dy in HUONG:
            if (x + dx, y + dy) not in dat:
                bo_bien += 1
    return bo_bien


def dem_dao(dat):
    da_tham = set()
    so_dao = 0
    for o in dat:
        if o in da_tham:
            continue
        so_dao += 1
        da_tham.add(o)
        hang_doi = [o]
        while hang_doi:
            x, y = hang_doi.pop()
            for dx, dy in HUONG:
                ke = (x + dx, y + dy)
                if ke in dat and ke not in da_tham:
                    da_tham.add(ke)
                    hang_doi.append(ke)
    return so_dao


dat = doc_ban_do()
print(dem_dao(dat), dem_bo_bien(dat))

Comments

There are no comments at the moment.