Editorial for Quần Đảo Pixel
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