Giả sử chúng ta có một lưới nước vô hạn. Chúng ta có thể thêm các khối đất vào lưới đó lần lượt. Chúng ta có một danh sách tọa độ gọi là land_requests, trong đó mỗi tọa độ có dạng [r, c] với r là hàng và c là cột. Chúng ta cần tìm một danh sách mà mỗi phần tử đại diện cho số lượng đảo tồn tại sau khi thêm từng khối đất từ land_requests.
Ví dụ, nếu đầu vào là land_requests = [[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]], thì đầu ra sẽ là [1, 2, 2, 2, 1].
Giải pháp
Sử dụng cấu trúc dữ liệu Union-Find (Disjoint Set Union) để theo dõi các thành phần liên thông:
- d := danh sách 4 hướng [(-1, 0), (0, 1), (1, 0), (0, -1)]
- idx := 0, mp := dictionary ánh xạ tọa độ -> chỉ số
- p := mảng parent, size := mảng kích thước thành phần
- comp := số lượng thành phần hiện tại (số đảo)
- ans := danh sách kết quả
- Hàm search(u): tìm gốc của u với nén đường
- Hàm connect(u, v): hợp nhất hai thành phần nếu khác gốc
- Duyệt qua từng request trong land_requests:
- Thêm đất mới, tăng comp
- Kiểm tra 4 hướng lân cận, nếu có đất thì connect
- Thêm comp vào ans
Ví dụ minh họa
d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
class Solution:
def search(self, u):
if u == self.p[u]:
return u
self.p[u] = self.search(self.p[u])
return self.p[u]
def connect(self, u, v):
pu = self.search(u)
pv = self.search(v)
if pu == pv:
return
self.comp -= 1
if self.size[pu] >= self.size[pv]:
self.p[pv] = pu
self.size[pu] += self.size[pv]
else:
self.p[pu] = pv
self.size[pv] += self.size[pu]
def solve(self, land_requests):
self.idx = 0
self.mp = dict()
self.p = []
self.size = []
self.comp = 0
ans = []
for request in land_requests:
i, j = request
self.mp[(i, j)] = self.idx
self.p.append(self.idx)
self.size.append(1)
self.idx += 1
self.comp += 1
for k in d:
ni = i + k[1]
nj = j + k[0]
if (ni, nj) in self.mp:
self.connect(self.mp[(i, j)], self.mp[(ni, nj)])
ans.append(self.comp)
return ans
ob = Solution()
land_requests = [[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]]
print(ob.solve(land_requests))
Đầu vào
[[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]]
Đầu ra
[1, 2, 2, 2, 1]