[Algorithm] 13. Matrix Traversal

13. Matrix Traversal

1.Flood Fill (LeetCode #733)

DFS-Recursive / DFS-Iterative / BFS

function floodFillDfsBfsAll(
  image: number[][],
  sr: number,
  sc: number,
  color: number
): number[][] {
  const originalColor = image[sr][sc];
  if (originalColor === color) return image;

  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  function dfsRecursive(row: number, col: number) {
    const isInRange =
      row >= 0 && row < image.length && col >= 0 && col < image[0].length;
    if (!isInRange || image[row][col] !== originalColor) return;

    image[row][col] = color;
    for (const [dx, dy] of directions) {
      dfsRecursive(row + dx, col + dy);
    }
  }

  // carefull with time limit exceed 
  function dfsIterative(row: number, col: number) {
    const stack: [number, number][] = [];
    stack.push([row, col]);
    while (stack.length > 0) {
      const [row, col] = stack.pop()!;

      image[row][col] = color;

      for (const [dx, dy] of directions) {
        const newX = row + dx;
        const newY = col + dy;

        const isInRange =
          newX >= 0 &&
          newX < image.length &&
          newY >= 0 &&
          newY < image[0].length;

        if (isInRange && image[newX][newY] === originalColor) {
          stack.push([newX, newY]);
        }
      }
    }
  }

  function bfs(row: number, col: number) {
    const queue: [number, number][] = [];
    queue.push([row, col]);

    while (queue.length > 0) {
      const [row, col] = queue.shift()!;
      image[row][col] = color;

      for (const [dx, dy] of directions) {
        const newX = row + dx;
        const newY = col + dy;

        const isInRange =
          newX >= 0 &&
          newX < image.length &&
          newY >= 0 &&
          newY < image[0].length;

        if (isInRange && image[newX][newY] === originalColor) {
          queue.push([newX, newY]);
        }
      }
    }
  }

  // dfsRecursive(sr, sc);
  // dfsIterative(sr, sc);
  bfs(sr, sc);

  return image;
}

2.Number of Islands (LeetCode #200)

BFS

// BFS
export function numIslands(grid: string[][]): number {
  if (grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let islandCnt = 0;

  // 4 directional
  const directions = [
    [0, 1], // right
    [0, -1], // left
    [1, 0], // down
    [-1, 0], // up
  ];

  function bfs(row: number, col: number) {
    let queue: [number, number][] = [[row, col]];
    grid[row][col] = "visited";

    while (queue.length > 0) {
      const [r, c] = queue.shift()!;
      for (const [dx, dy] of directions) {
        const newX = r + dx;
        const newY = c + dy;

        if (
          newX >= 0 &&
          newX < rows &&
          newY >= 0 &&
          newY < cols &&
          grid[newX][newY] === "1"
        ) {
          queue.push([newX, newY]);
          grid[newX][newY] = "visited";
        }
      }
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1") {
        islandCnt++;
        bfs(r, c);
      }
    }
  }

  
  return islandCnt;
}

DFS (Caution! Call Stack Exceeded)

function numIslandsDFS(grid: string[][]): number {
  if (grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let isalandCnt = 0;

  // 4 directional
  const directions = [
    [0, 1], // right
    [0, -1], // left
    [1, 0], // down
    [-1, 0], // up
  ];

  function dfs(row: number, col: number) {
    if (
      row < 0 ||
      row >= rows ||
      col < 0 ||
      col >= cols ||
      grid[row][col] === "0"
    )
      return;

    grid[row][col] = "visited";
    for (const [dx, dy] of directions) {
      const newX = row + dx;
      const newY = row + dy;
      dfs(newX, newY);
    }
  }

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === "1") {
        isalandCnt++;
        dfs(col, col);
      }
    }
  }

  return 0;
}

3.Surrounded Regions (LeetCode #130)

// 문제가 보더에 인접한 "O"만 "X"로 안바꾼다.
// as is
// [
//   ["X", "O", "X", "X"],
//   ["O", "O", "X", "X"],
//   ["X", "O", "O", "X"],
//   ["X", "X", "X", "X"],
// ]

//  to be
//  [ 'X', 'O', 'X', 'X' ],
//  [ 'O', 'X', 'X', 'X' ],
//  [ 'X', 'X', 'X', 'X' ],
//  [ 'X', 'X', 'X', 'X' ]


export function surroundedRegionsWhichNotConnectedBoard(board: string[][]): void {
  if (board.length === 0) return;

  const rows = board.length;
  const cols = board[0].length;

  const queue: [number, number][] = [];

  // 4 directional movement
  const directions = [
    [0, 1], // right
    [0, -1], // left
    [1, 0], // down
    [-1, 0], // up
  ];

  // **Step 1: Find 'O's on the edges and mark them as '#'**
  function markBorderConnected(row: number, col: number) {
    if (board[row][col] !== "O") return;
    board[row][col] = "#";
    queue.push([row, col]);
  }

  // Mark all 'O's on the borders
  for (let r = 0; r < rows; r++) {
    markBorderConnected(r, 0); // Left border
    markBorderConnected(r, cols - 1); // Right border
  }
  for (let c = 0; c < cols; c++) {
    markBorderConnected(0, c); // Top border
    markBorderConnected(rows - 1, c); // Bottom border
  }

  // **Step 2: BFS to mark all connected 'O's from the border**
  while (queue.length > 0) {
    const [r, c] = queue.shift()!;
    for (const [dx, dy] of directions) {
      const newX = r + dx;
      const newY = c + dy;
      if (
        newX >= 0 &&
        newX < rows &&
        newY >= 0 &&
        newY < cols &&
        board[newX][newY] === "O"
      ) {
        board[newX][newY] = "#";
        queue.push([newX, newY]);
      }
    }
  }

  // **Step 3: Convert remaining 'O's to 'X' and '#' back to 'O'**
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === "O") board[r][c] = "X";
      else if (board[r][c] === "#") board[r][c] = "O";
    }
  }
}