Chương 12 - Island Matrix Traversal

Grid 2D thực ra là graph ngầm: mỗi ô là 1 node, 4 ô kề (lên/xuống/trái/ phải) là cạnh. Mọi bài “đảo” / “tô màu vùng” / “flood fill” đều là DFS/BFS trên graph này. Chương này dạy bạn 4 trick đặc trưng cho grid: (1) flood fill, (2) multi-source BFS từ biên, (3) reverse thinking (đánh dấu cái không cần), (4) mutate input để mark visited.

Mục tiêu chương

Sau chương này, bạn sẽ:

• Thuộc 4 trick grid: flood fill, multi-source biên, reverse thinking, mutate input.
• Phân biệt in-place marking vs visited set tradeoff.
• Thuộc direction array idiom + bounds check.
• Gateway sang Union Find (Ch 24) cho online add-land.

Khi nào dùng pattern này?

• Đề bài cho grid: List[List[T]] với cell có 2-3 trạng thái.
• Câu hỏi: đếm/đo vùng liên thông, tô màu, lan toả, ranh giới.
• Có 2 hướng tư duy chính:
  • Forward: BFS/DFS từ ô interest, đếm/đo.
  • Reverse: tìm các ô KHÔNG thoả điều kiện (vd. nối với biên), suy ra cái còn lại là đáp án.

Template code

from collections import deque
from typing import List

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 1) Flood fill DFS (đệ quy)
def flood_fill(grid: List[List[int]], r: int, c: int, marker: int) -> int:
    rows, cols = len(grid), len(grid[0])
    if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
        return 0
    grid[r][c] = marker             # mark visited
    size = 1
    for dr, dc in DIRS:
        size += flood_fill(grid, r + dr, c + dc, marker)
    return size


# 2) Multi-source BFS từ tất cả biên hoặc tất cả ô đặc biệt
def multi_source_bfs(grid, sources):
    queue = deque(sources)
    visited = set(sources)
    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc))
    return visited

Bài tự luyện cuối chương

• LC 463 - Island Perimeter
• LC 733 - Flood Fill
• LC 994 - Rotting Oranges (Chương 10)
• LC 1020 - Number of Enclaves
• LC 1254 - Number of Closed Islands
• LC 1905 - Count Sub Islands

---

12.1 Number of Islands (LC 200)

Đề bài

Cho grid m × n với '1' = đất, '0' = nước. Đảo là vùng đất liên thông (4 hướng). Đếm số đảo.

Ví dụ

Input:
[["1","1","1","1","0"],
 ["1","1","0","1","0"],
 ["1","1","0","0","0"],
 ["0","0","0","0","0"]]
Output: 1   (cả vùng "1" liên thông)

Input:
[["1","1","0","0","0"],
 ["1","1","0","0","0"],
 ["0","0","1","0","0"],
 ["0","0","0","1","1"]]
Output: 3   (góc trái-trên, giữa, góc phải-dưới)

Ràng buộc

• 1 <= m, n <= 300

Clarifying questions

• Có sửa grid được không? → Có (mutate cho gọn).
• Grid rỗng? → Trả 0.

Hướng tiếp cận

Pattern flood fill kinh điển. Duyệt mỗi ô: - Nếu là '1' và chưa visited → tăng counter, gọi DFS/BFS đánh dấu toàn bộ đảo này thành visited (đổi '1' → '0' để khỏi dùng set riêng).

Hình minh hoạ với grid 4×5 thứ 2:

Bước 1, ô (0,0) = '1' → DFS:
[1 1 0 0 0]      [* * 0 0 0]
[1 1 0 0 0]  →   [* * 0 0 0]
[0 0 1 0 0]      [0 0 1 0 0]
[0 0 0 1 1]      [0 0 0 1 1]
                 (đảo 1 đánh dấu)

Bước 2, gặp ô (2,2) = '1' → DFS (chỉ đánh dấu chính nó):
[* * 0 0 0]
[* * 0 0 0]
[0 0 * 0 0]
[0 0 0 1 1]

Bước 3, gặp ô (3,3) = '1' → DFS:
[* * 0 0 0]
[* * 0 0 0]
[0 0 * 0 0]
[0 0 0 * *]

Đếm: 3 đảo

Code Python 3

from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        rows, cols = len(grid), len(grid[0])
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(r: int, c: int) -> None:
            if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != '1':
                return
            grid[r][c] = '0'              # mark visited
            for dr, dc in DIRS:
                dfs(r + dr, c + dc)

        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    dfs(r, c)
        return count

Phân tích độ phức tạp

• Thời gian: O(m · n). Bộ nhớ: O(m · n) worst-case stack với grid toàn ‘1’.

Bình luận

• Mutate input vs visited set:
  • Mutate (đổi ‘1’ → ‘0’): tiết kiệm space, code gọn.
  • Visited set: không phá input - phải nếu interviewer cấm.
  • Luôn hỏi rõ trước khi mutate.
• Stack overflow: với grid 300×300 toàn ‘1’ (90,000 ô), DFS đệ quy có thể RecursionError. Fallback: BFS bằng deque.
• Liên hệ: đây là bài gateway cho Chương 24 (Union Find) - cùng vấn đề counts connected components.

Bài tự luyện liên quan

• LC 695 - Max Area of Island (bài 12.2).
• LC 305 - Number of Islands II (Union Find).
• LC 463 - Island Perimeter.

---

12.2 Max Area of Island (LC 695)

Đề bài

Cùng grid với 0/1. Trả về diện tích lớn nhất của một đảo (số ô ‘1’ của nó), hoặc 0 nếu không có đảo nào.

Ví dụ

Input:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6

Ràng buộc

• 1 <= m, n <= 50
• grid[i][j] ∈ {0, 1}

Clarifying questions

• Đảo lớn nhất có thể là 0 (không có đảo)? → Có, trả 0.

Hướng tiếp cận

Variant của bài 12.1, nhưng DFS trả về size thay vì void. Lấy max qua các lần khởi động DFS.

Code Python 3

from typing import List

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(r: int, c: int) -> int:
            if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
                return 0
            grid[r][c] = 0
            return 1 + sum(dfs(r + dr, c + dc) for dr, dc in DIRS)

        best = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    best = max(best, dfs(r, c))
        return best

Phân tích độ phức tạp

• Thời gian: O(m · n). Bộ nhớ: O(m · n) worst stack.

Bình luận

• Trick 1 + sum(...) rất Pythonic. Mỗi hàng xóm đệ quy trả về số ô trong phần “đảo nối từ nó”, cộng 1 cho chính ô đang DFS.
• Follow-up - LC 827 - Making A Large Island: cho phép đổi 1 ô 0 → 1, tìm đảo lớn nhất sau khi đổi. Tăng độ phức tạp đáng kể: phải label từng đảo trước.

Bài tự luyện liên quan

• LC 200 - Number of Islands.
• LC 463 - Island Perimeter.
• LC 827 - Making A Large Island.

---

12.3 Surrounded Regions (LC 130)

Đề bài

Cho grid chứa 'X' và 'O'. Lật mọi vùng 'O' được bao quanh hoàn toàn bởi 'X' (vùng không chạm biên grid) thành 'X'. Vùng 'O' chạm biên được giữ nguyên.

Ví dụ

Input:  board = [['X','X','X','X'],
                 ['X','O','O','X'],
                 ['X','X','O','X'],
                 ['X','O','X','X']]
Output: board = [['X','X','X','X'],
                 ['X','X','X','X'],
                 ['X','X','X','X'],
                 ['X','O','X','X']]

(mutate in-place; 'O' ở (3,1) chạm biên dưới → giữ;
 cụm 'O' bên trong bị bao quanh → lật thành 'X')

Ràng buộc

• 1 <= m, n <= 200

Clarifying questions

• Có sửa board không? → Yêu cầu in-place.
• Vùng O nhỏ nhất là 1 ô? → Có.

Hướng tiếp cận

Reverse thinking - đây là pattern cực hay: - Thay vì tìm vùng 'O' bị bao, ta tìm vùng 'O' chạm biên (rất dễ). - Đánh dấu chúng (vd. đổi tạm thành '#'). - Cuối cùng: - '#' → 'O' (giữ). - 'O' còn lại → 'X' (lật).

Hình minh hoạ:

Grid ban đầu:               Sau DFS từ các 'O' biên (đánh dấu '#'):
X X X X                     X X X X
X O O X                     X O O X     (O ở (1,1),(1,2) KHÔNG chạm biên,
X X O X         →           X X O X       không bị mark)
X O X X                     X # X X     (O ở (3,1) chạm biên → mark)

Quét cuối:
'#' → 'O'; 'O' → 'X':
X X X X
X X X X
X X X X
X O X X

Code Python 3

from typing import List

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board:
            return
        rows, cols = len(board), len(board[0])

        def dfs(r: int, c: int) -> None:
            if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != 'O':
                return
            board[r][c] = '#'
            dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)

        # 1. DFS từ mọi 'O' ở biên - mark thành '#'.
        for r in range(rows):
            dfs(r, 0)
            dfs(r, cols - 1)
        for c in range(cols):
            dfs(0, c)
            dfs(rows - 1, c)

        # 2. Lật: '#' → 'O' (giữ); 'O' → 'X' (lật).
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == '#':
                    board[r][c] = 'O'

Phân tích độ phức tạp

• Thời gian: O(m · n). Bộ nhớ: O(m · n) stack worst-case.

Bình luận

• Tại sao reverse thinking? Vì check một O có bị bao không đòi hỏi duyệt cả vùng và kiểm tra mọi biên đảo - phức tạp. Ngược lại, có chạm biên không là 1 query khi đã đánh dấu xong.
• Mutate input ở đây là bắt buộc theo đề (in-place modification).
• Liên kết: pattern này tái xuất ở LC 1020, 1254.

Bài tự luyện liên quan

• LC 1020 - Number of Enclaves.
• LC 1254 - Number of Closed Islands.
• LC 417 - Pacific Atlantic Water Flow (bài 12.4).

---

12.4 Pacific Atlantic Water Flow (LC 417)

Đề bài

Cho ma trận chiều cao heights[i][j] đại diện chiều cao đảo. Mép trái và mép trên giáp Thái Bình Dương; mép phải và mép dưới giáp Đại Tây Dương. Nước chảy từ ô (r, c) sang ô kề có chiều cao ≤ (r, c).

Trả về tất cả (r, c) mà nước từ đó có thể chảy ra cả 2 đại dương.

Ví dụ

Input:  heights = [[1,2,2,3,5],
                   [3,2,3,4,4],
                   [2,4,5,3,1],
                   [6,7,1,4,5],
                   [5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Ràng buộc

• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 10^5

Clarifying questions

• Mức nước có thể đi ngang (cùng cao)? → Có (≤, không strict).

Hướng tiếp cận

Forward thinking - TLE. Với mỗi ô, BFS xem chảy được ra biên nào. Worst-case O((mn)²).

Reverse thinking - O(m · n).

Thay vì hỏi “ô nào chảy được ra biển?”, ta hỏi “biển có thể vươn lên tới ô nào?”. Biển vươn lên cao theo quy tắc: chỉ vào ô có chiều cao ≥ ô hiện tại.

• 2 BFS / DFS xuất phát từ biên Pacific và biên Atlantic riêng.
• Giao của 2 tập = đáp án.

Hình minh hoạ - Pacific reach (P) và Atlantic reach (A) trên ma trận 5x5:

P P P P P/A                   A A A A A
P . . . A             P/A . . . A
P . . . A             P . . . A
P/A . . . A             P . . . A
P/A A A A A             P P P P P

Giao P ∩ A = các ô có cả 2 → đáp án.

Code Python 3

from typing import List

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        if not heights:
            return []
        rows, cols = len(heights), len(heights[0])
        pacific: set[tuple[int, int]] = set()
        atlantic: set[tuple[int, int]] = set()

        def dfs(r: int, c: int, visited: set, prev_h: int) -> None:
            if (r, c) in visited:
                return
            if not (0 <= r < rows and 0 <= c < cols):
                return
            if heights[r][c] < prev_h:    # biển không vươn được vào ô thấp hơn
                return
            visited.add((r, c))
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                dfs(r + dr, c + dc, visited, heights[r][c])

        # Pacific: biên trái + biên trên.
        for r in range(rows):
            dfs(r, 0, pacific, heights[r][0])
        for c in range(cols):
            dfs(0, c, pacific, heights[0][c])
        # Atlantic: biên phải + biên dưới.
        for r in range(rows):
            dfs(r, cols - 1, atlantic, heights[r][cols - 1])
        for c in range(cols):
            dfs(rows - 1, c, atlantic, heights[rows - 1][c])

        return [[r, c] for r, c in pacific & atlantic]

Phân tích độ phức tạp

• Thời gian: O(m · n) - mỗi ô được thăm tối đa 2 lần (1 cho mỗi đại dương).
• Bộ nhớ: O(m · n).

Bình luận

• Reverse thinking (“đi từ kết quả ngược về input”) là kỹ năng hay gặp ở các bài Big Tech. Bài này cùng pattern với Surrounded Regions, 01 Matrix.
• Bẫy: điều kiện flow ngược - biển chỉ “vươn lên” ô có chiều cao không thấp hơn ô hiện tại (>=, không phải <=).

Bài tự luyện liên quan

• LC 130 - Surrounded Regions.
• LC 1254 - Number of Closed Islands.

---

12.5 Walls and Gates (LC 286)

Đề bài

Cho rooms: ma trận m × n các số nguyên với 3 giá trị có ý nghĩa: - -1 = tường (cản đường). - 0 = cổng (gate). - INF (= 2³¹ - 1) = phòng trống.

Điền vào mỗi phòng trống khoảng cách ngắn nhất (số bước 4 hướng) đến cổng gần nhất. Nếu phòng không đến được cổng nào, giữ INF.

Ví dụ

Input:  rooms = [[INF, -1,  0, INF],
                 [INF,INF,INF, -1],
                 [INF, -1,INF, -1],
                 [  0, -1,INF,INF]]
        (-1 = tường, 0 = cổng, INF = phòng trống)

Output: rooms = [[3, -1, 0, 1],
                 [2,  2, 1,-1],
                 [1, -1, 2,-1],
                 [0, -1, 3, 4]]
        (mutate in-place; mỗi ô = khoảng cách 4 hướng tới cổng gần nhất)

Ràng buộc

• 1 <= m, n <= 250
• rooms[i][j] ∈ {-1, 0, INF}

Clarifying questions

• Có tường chia phòng không tới cửa? → Có, giữ INF.
• Phòng đã là 0 (cổng)? → Skip.

Hướng tiếp cận

Multi-source BFS - đẩy tất cả các cổng vào queue cùng lúc. Lan toả ra ngoài, mỗi ô đặt distance = số bước từ cổng gần nhất.

Vì sao multi-source > BFS từng cổng? Multi-source O(mn), BFS từng cổng O(gates · mn) - gates có thể O(mn).

Code Python 3

from collections import deque
from typing import List

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        if not rooms:
            return
        rows, cols = len(rooms), len(rooms[0])
        queue: deque[tuple[int, int]] = deque()
        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == 0:
                    queue.append((r, c))

        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while queue:
            r, c = queue.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                # Chỉ "ghi" vào ô INF - vì BFS, lần đầu ghi đã là min.
                if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == 2147483647:
                    rooms[nr][nc] = rooms[r][c] + 1
                    queue.append((nr, nc))

Phân tích độ phức tạp

• Thời gian: O(m · n). Bộ nhớ: O(m · n).

Bình luận

• Tại sao multi-source cho ra đúng min distance? BFS có invariant: lần đầu ghi vào 1 ô là khoảng cách ngắn nhất. Đẩy tất cả cổng vào level 0 → ô được ghi từ cổng nào gần nhất.
• Bẫy: không check rooms[nr][nc] == INF → ghi đè vào 0 (cổng khác) hoặc -1 (tường).

Bài tự luyện liên quan

• LC 994 - Rotting Oranges.
• LC 542 - 01 Matrix (bài 12.6).
• LC 317 - Shortest Distance from All Buildings.

---

12.6 01 Matrix (LC 542)

Đề bài

Cho ma trận mat chỉ chứa 0 và 1. Trả về ma trận cùng kích thước, mỗi ô = khoảng cách (số bước 4 hướng) đến số 0 gần nhất.

Ví dụ

Input:  mat = [[0,0,0],
               [0,1,0],
               [1,1,1]]
Output:       [[0,0,0],
               [0,1,0],
               [1,2,1]]
        (mỗi ô = khoảng cách Manhattan tới ô '0' gần nhất)

Ràng buộc

• 1 <= m, n <= 10^4
• mat[i][j] ∈ {0, 1}

Clarifying questions

• Toàn 0? → Output toàn 0.
• Toàn 1? → Có thể không có 0 → vẫn có grid (1 lớp ô = INF).

Hướng tiếp cận

Y hệt Walls and Gates: multi-source BFS từ tất cả ô 0. Distance ban đầu của ô 0 = 0, các ô 1 chưa biết.

Cách khác - DP 2 lượt, O(m · n): - Lượt 1 (trên-trái → dưới-phải): dp[r][c] = min(dp[r-1][c], dp[r][c-1]) + 1. - Lượt 2 (dưới-phải → trên-trái): dp[r][c] = min(dp[r][c], dp[r+1][c]+1, dp[r][c+1]+1).

Cả 2 đều O(m · n). BFS trực quan hơn; DP gọn space.

Code Python 3

from collections import deque
from typing import List

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        INF = float('inf')
        dist = [[INF] * cols for _ in range(rows)]

        queue: deque[tuple[int, int]] = deque()
        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    dist[r][c] = 0
                    queue.append((r, c))

        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while queue:
            r, c = queue.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] > dist[r][c] + 1:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
        return dist


class SolutionDP:
    """Cách DP 2 lượt - gọn space (in-place khi cho phép)."""

    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        INF = rows + cols + 1
        dist = [[0 if mat[r][c] == 0 else INF
                 for c in range(cols)] for r in range(rows)]
        # Lượt 1: trên-trái → dưới-phải.
        for r in range(rows):
            for c in range(cols):
                if dist[r][c] == 0:
                    continue
                top = dist[r-1][c] if r > 0 else INF
                left = dist[r][c-1] if c > 0 else INF
                dist[r][c] = min(top, left) + 1
        # Lượt 2: dưới-phải → trên-trái.
        for r in range(rows - 1, -1, -1):
            for c in range(cols - 1, -1, -1):
                if dist[r][c] == 0:
                    continue
                bot = dist[r+1][c] + 1 if r < rows - 1 else INF
                right = dist[r][c+1] + 1 if c < cols - 1 else INF
                dist[r][c] = min(dist[r][c], bot, right)
        return dist

Phân tích độ phức tạp

• Thời gian: O(m · n). Bộ nhớ: O(m · n).

Bình luận

• DP 2 lượt có tinh thần “duyệt 1 chiều rồi duyệt ngược lại để truyền thông tin từ 2 phía”. Pattern này còn xuất hiện ở LC 84 (Largest Rectangle from histogram) cách non-stack, …
• Bẫy DP: nhớ tránh out-of-bound (dùng INF ở các ô ngoài).

Bài tự luyện liên quan

• LC 286 - Walls and Gates.
• LC 994 - Rotting Oranges.
• LC 1162 - As Far From Land as Possible.

Tóm tắt chương & Quyết định

Matrix traversal checklist

1. Direction array: dirs = [(-1,0),(1,0),(0,-1),(0,1)] (4-conn) hoặc 8-conn.
2. Bounds: 0 <= nr < R and 0 <= nc < C.
3. Visited: in-place mark (đổi '1' → '0' hoặc #) hay set?
4. Mutation OK? Hỏi interviewer; nếu không, dùng visited 2D.
5. Stack overflow với DFS đệ quy: grid 1000×1000 có thể vượt limit. Dùng iterative stack hoặc BFS.

Boundary-first technique

Cho bài Surrounded Regions (LC 130) và Pacific Atlantic (LC 417): - “Cell không thoả điều kiện” = cell kết nối với biên. - Seed BFS/DFS từ biên, đánh dấu cell reach được; cell còn lại là cell bị bao quanh.

Multi-source BFS

Cho 01 Matrix (LC 542) và Walls and Gates (LC 286): - Bỏ tất cả nguồn vào queue ban đầu (cell 0 cho 542, cổng 0 cho 286). - BFS level → distance lan ra. Mỗi cell được visit một lần ⇒ O(R·C).

In-place mark vs visited set

Tiêu chí	In-place	Set/2D bool
Bộ nhớ phụ	O(1)	O(R·C)
Mutate input?	Có	Không
Concurrency/restore	Khó	Dễ
Ưu tiên	Khi cho phép & cần O(1) extra	Khi grid immutable hoặc cần re-run

---