130.被围绕的区域

链接：130.被围绕的区域
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵
简介：给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

题解 1 - typescript

• 编辑时间：2021-07-25
• 执行用时：96ms
• 内存消耗：42.9MB
• 编程语言：typescript
• 解法介绍：dfs。

function solve(board: string[][]): void {
  const n = board.length;
  const m = board[0].length;
  for (let i = 0; i < n; i++) {
    dfs(i, 0);
    dfs(i, m - 1);
  }
  for (let i = 0; i < m; i++) {
    dfs(0, i);
    dfs(n - 1, i);
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (board[i][j] === 'O') board[i][j] = 'X';
      if (board[i][j] === 'A') board[i][j] = 'O';
    }
  }
  function dfs(row: number, col: number): void {
    if (board[row][col] !== 'O') return;
    board[row][col] = 'A';
    if (row > 0) dfs(row - 1, col);
    if (col > 0) dfs(row, col - 1);
    if (row < n - 1) dfs(row + 1, col);
    if (col < m - 1) dfs(row, col + 1);
  }
}

题解 2 - typescript

• 编辑时间：2020-08-11
• 执行用时：132ms
• 内存消耗：41MB
• 编程语言：typescript
• 解法介绍：从边缘开始找，进行深度优先搜索。

function solve(board: string[][]): void {
  const row = board.length;
  if (row === 0) return;
  const col = board[0].length;
  const isEdge = (i: number, j: number): boolean =>
    i === 0 || j === 0 || i === row - 1 || j === col - 1;
  const check = (i: number, j: number): void => {
    const tag = board[i][j];
    if (tag === 'O') {
      board[i][j] = 'A';
      dfs(i, j);
    }
  };
  const dfs = (i: number, j: number): void => {
    // top
    if (i !== 0 && !isEdge(i - 1, j) && board[i - 1][j] === 'O') {
      board[i - 1][j] = 'A';
      dfs(i - 1, j);
    }
    // bottom
    if (i !== row - 1 && !isEdge(i + 1, j) && board[i + 1][j] === 'O') {
      board[i + 1][j] = 'A';
      dfs(i + 1, j);
    }
    // left
    if (j !== 0 && !isEdge(i, j - 1) && board[i][j - 1] === 'O') {
      board[i][j - 1] = 'A';
      dfs(i, j - 1);
    }
    // right
    if (j !== col - 1 && !isEdge(i, j + 1) && board[i][j + 1] === 'O') {
      board[i][j + 1] = 'A';
      dfs(i, j + 1);
    }
  };
  // top bottom
  for (let j = 0; j < col; j++) {
    check(0, j);
    check(row - 1, j);
  }
  // left right
  for (let i = 0; i < row; i++) {
    check(i, 0);
    check(i, col - 1);
  }
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      const tag = board[i][j];
      if (tag === 'O') board[i][j] = 'X';
      else if (tag === 'A') board[i][j] = 'O';
    }
  }
}