Number of Islands — đếm số đảo trong lưới '1'/'0' bằng DFS? Vì sao phải đánh dấu ô đã thăm?

Ý tưởng: Quét toàn lưới; gặp ô '1' chưa thăm thì tăng đếm đảo lên 1 và "chìm" cả đảo đó bằng DFS (đổi mọi ô '1' liền kề thành '0'). Mỗi lần khởi DFS = một đảo mới.

Vì sao đánh dấu: không đánh dấu thì DFS quay lại ô cũ → lặp vô tận và đếm trùng. Sửa tại chỗ thành '0' đóng luôn vai trò "visited".

function numIslands(grid: string[][]): number {
  const rows = grid.length, cols = grid[0].length
  let count = 0
  const dfs = (r: number, c: number) => {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') return
    grid[r][c] = '0' // đánh dấu đã thăm
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
  }
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === '1') { count++; dfs(r, c) }
  return count
}

Độ phức tạp: thời gian O(rows×cols), bộ nhớ O(rows×cols) cho stack đệ quy xấu nhất.

Lưu ý: Nếu không được sửa input, dùng mảng visited riêng. Lưới rất lớn nên đổi sang BFS (queue) để tránh stack overflow.

Idea: Scan the grid; on an unvisited '1', increment the island count and "sink" the whole island via DFS (flip every adjacent '1' to '0'). Each DFS launch = one new island.

Why mark: without marking, DFS revisits cells → infinite loop and double counting. Mutating to '0' doubles as the "visited" flag.

function numIslands(grid: string[][]): number {
  const rows = grid.length, cols = grid[0].length
  let count = 0
  const dfs = (r: number, c: number) => {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') return
    grid[r][c] = '0' // mark visited
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
  }
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === '1') { count++; dfs(r, c) }
  return count
}

Complexity: time O(rows×cols), space O(rows×cols) for the recursion stack worst case.

Note: If mutating the input isn't allowed, use a separate visited array. For very large grids switch to BFS (queue) to avoid stack overflow.