Number of Islands
Bạn nhận được một bản đồ dưới dạng danh sách (list) các chuỗi (string) có độ dài bằng nhau, trong đó '1' là một ô đất và '0' là một ô nước. Hai ô đất thuộc cùng một hòn đảo nếu chúng chung một cạnh: trên, dưới, trái hoặc phải. Các ô chỉ chạm nhau ở góc thì không được tính là kết nối. Hãy trả về số hòn đảo.
Hàm
- gridstring-array
- mảng, mỗi hàng một chuỗi
- Trả vềinteger
- số lượng đảo
Ràng buộc
1 ≤ grid.length ≤ 1501 ≤ grid[i].length ≤ 150- Mọi hàng đều có cùng độ dài.
- Mỗi ký tự đều là
'0'hoặc'1'.
Ví dụ
- Đầu vào
- grid = ["11000", "11000", "00100", "00011"]
- Đầu ra
- 3
- Giải thích
- Bốn ô vuông ở góc trên bên trái tạo thành một hòn đảo. Ô vuông ở giữa hàng thứ ba chỉ chạm vào chúng ở một góc, nên đó là hòn đảo thứ hai. Cặp ô vuông ở góc dưới bên phải là hòn đảo thứ ba.
- Đầu vào
- grid = ["01110", "01000", "00011", "11001"]
- Đầu ra
- 3
- Giải thích
- Ba ô ở hàng trên cùng và ô bên dưới đầu bên trái tạo thành một hòn đảo. Cặp ô bên phải ở hàng thứ ba nối xuống ô dưới cùng bên phải, tạo thành hòn đảo thứ hai. Cặp ô dưới cùng bên trái là hòn đảo thứ ba.
Câu hỏi mở rộng
Đất liền giờ xuất hiện từng ô một trên bản đồ nước. Bạn có thể báo số lượng hòn đảo sau mỗi ô mới mà không cần quét lại toàn bộ bản đồ không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Quét bản đồ theo từng ô. Khi đến một ô đất chưa thuộc về hòn đảo nào trước đó, bạn đã tìm thấy thêm bao nhiêu hòn đảo?
Khi tìm thấy một hòn đảo mới, hãy đi đến mọi ô đất nối với hòn đảo đó và đánh dấu từng ô là đã thấy, để lần quét không đếm lại cùng một hòn đảo.
Khám phá bằng một hàng đợi (theo chiều rộng) hoặc một ngăn xếp tường minh (theo chiều sâu) chứa các ô chưa ghé thăm. Tìm kiếm đệ quy có thể làm cạn ngăn xếp lời gọi trên bản đồ có một hòn đảo khổng lồ, còn vòng lặp dùng hàng đợi hoặc ngăn xếp của riêng bạn thì không.
Lời giải
Xem mỗi ô đất là một nút nối với các ô đất bên cạnh: một hòn đảo là một vùng đất liền thông nhau. Duyệt bản đồ, mỗi khi gặp ô đất chưa từng thấy, hãy đếm đó là một hòn đảo mới rồi tô loang, đánh dấu mọi ô thuộc hòn đảo đó để lần duyệt sau không đếm lại.
Lấp vùng bằng ngăn xếp tường minh (DFS)
Ý tưởng
Một ô đất chưa được đánh dấu không thể thuộc về hòn đảo bạn đã đếm, vì khi đếm một hòn đảo, bạn đánh dấu toàn bộ hòn đảo đó. Vì vậy, ô này bắt đầu một hòn đảo mới. Một ngăn xếp do bạn tự quản lý sẽ đánh dấu phần còn lại: mỗi ô bạn lấy ra sẽ đẩy các ô đất láng giềng chưa được đánh dấu vào ngăn xếp, và khi ngăn xếp trống, toàn bộ hòn đảo đã được đánh dấu.
Ngăn xếp tự quản lý rất quan trọng vì thuật toán lan truyền đệ quy có thể sâu đến 22,500 lời gọi trên bản đồ đất liền kín có kích thước 150 × 150. Mỗi ô được đẩy vào ngăn xếp nhiều nhất một lần và kiểm tra bốn ô láng giềng, nên thời gian là O(rows × cols). Các dấu đánh dấu và ngăn xếp chiếm O(rows × cols) bộ nhớ khi bản đồ toàn là đất liền.
Thuật toán
- Tạo dấu đã thăm cho mỗi ô vuông và đặt số đếm về 0.
- Duyệt qua từng ô vuông, bỏ qua nước và những ô đã thăm.
- Với ô đất chưa thăm, tăng số đếm thêm 1, đánh dấu ô đó rồi đẩy nó vào ngăn xếp.
- Khi ngăn xếp chưa rỗng, lấy một ô vuông ra rồi đẩy từng ô lân cận nằm trong bản đồ và là đất chưa thăm vào ngăn xếp, đồng thời đánh dấu ô đó trước khi đẩy.
- Trả về số đếm khi kết thúc lượt duyệt.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
# Land that no island has claimed yet: a new island.
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
# Mark on push, so no square enters the stack twice.
seen[ni][nj] = True
stack.append((ni, nj))
return countFlood fill bằng hàng đợi (BFS)
Ý tưởng
Cách đếm vẫn như vậy, chỉ có thứ tự thăm thay đổi. Hàng đợi lấy các ô từ đầu hàng đợi và thêm những ô đất lân cận chưa được đánh dấu vào cuối hàng đợi, vì vậy nó thăm hòn đảo theo từng vòng: ô đầu tiên, rồi tất cả ô cách một bước, sau đó là những ô cách hai bước. Mỗi ô vẫn chỉ được thăm một lần, với thời gian và không gian O(rows × cols).
Thứ tự theo vòng cho biết khoảng cách từ điểm bắt đầu đến mỗi ô, vì vậy cùng vòng lặp đó có thể trả lời các câu hỏi về đường đi ngắn nhất trên lưới, chỉ cần thêm một con số cho mỗi ô.
Thuật toán
- Tạo một dấu đã thăm cho mỗi ô vuông và đặt số đếm bằng 0.
- Quét từng ô vuông, bỏ qua nước và các ô đã được đánh dấu.
- Trên vùng đất chưa được đánh dấu, tăng số đếm thêm 1, đánh dấu ô vuông rồi đưa ô đó vào hàng đợi trống.
- Khi hàng đợi còn ô vuông, lấy một ô ở đầu hàng đợi rồi thêm từng ô lân cận nằm trong bản đồ và là đất chưa được đánh dấu vào cuối hàng đợi, đồng thời đánh dấu các ô đó khi thêm vào.
- Trả về số đếm khi quá trình quét kết thúc.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
seen[ni][nj] = True
stack.append((ni, nj))
return count
Lỗi thường gặp và trường hợp biên
- Đánh dấu một ô vuông khi lấy ô đó ra khỏi ngăn xếp hoặc hàng đợi, thay vì khi thêm ô vào. Khi đó, cùng một ô vuông sẽ được thêm vào nhiều lần.
- So sánh một ô vuông với số 1 thay vì ký tự
'1'. Mỗi hàng là một chuỗi, nên mỗi ô vuông là một ký tự. - Đọc một ô lân cận trước khi kiểm tra
0 ≤ row < rowsvà0 ≤ col < cols. Khi đó, ô đất ở rìa sẽ khiến chương trình đọc ra ngoài bản đồ. - Viết thuật toán tô vùng bằng đệ quy. Theo mặc định, Python dừng sau 1,000 lần gọi, còn các ngôn ngữ khác có thể làm tràn ngăn xếp khi gặp một hòn đảo lớn.
- Lấy phần tử đầu của danh sách Python bằng
pop(0), thao tác này tốn thời gian tỷ lệ thuận với độ dài danh sách. Hãy dùngcollections.dequevàpopleft().
Câu hỏi thường gặp4
Độ phức tạp thời gian của bài toán Số lượng đảo là bao nhiêu?
O(rows × cols). Lần quét xem xét mỗi ô một lần, mỗi ô đất được đưa vào ngăn xếp hoặc hàng đợi một lần và kiểm tra bốn ô lân cận. Các dấu đã thăm và ngăn xếp hoặc hàng đợi dùng O(rows × cols) bộ nhớ trên bản đồ toàn đất.
Bạn nên dùng BFS hay DFS cho bài toán Số lượng đảo?
Cả hai đều chính xác và có độ phức tạp thời gian, không gian như nhau, vì việc đếm chỉ cần đánh dấu mọi ô vuông của một hòn đảo. BFS dùng hàng đợi nên không bao giờ đệ quy; DFS cũng an toàn như vậy khi dùng ngăn xếp tường minh.
Bạn có thể giải bài toán Number of Islands bằng cấu trúc union-find không?
Đúng vậy. Đưa mỗi ô đất vào một tập hợp (set) riêng và bắt đầu đếm từ số ô đất. Gộp từng cặp ô đất liền kề, rồi giảm số đếm đi một mỗi khi phép gộp kết nối hai tập hợp khác nhau. Với kỹ thuật nén đường đi (path compression), thời gian chạy gần bằng O(rows × cols).
Bạn có thể đếm số đảo mà không cần một mảng riêng để lưu các đảo đã thấy không?
Đúng vậy, nếu bạn có thể thay đổi bản đồ: hãy đổi mỗi ô đất thành nước ngay khi bạn đến đó. Nhiều ngôn ngữ không thể thay đổi chuỗi tại chỗ, vì vậy trước tiên bạn sao chép các hàng vào một lưới ký tự, việc này tốn lượng bộ nhớ bằng với các dấu đã đánh dấu.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def numIslands(grid):
# Viết code tại đâyKiểm thử #1
Kiểm thử #2
Đối số
grid = ["11000", "11000", "00100", "00011"]
Đầu ra mong đợi
3