130.被围绕的区域

被围绕的区域

给你一个 m x n 的矩阵 board，由若干字符 ‘X’ 和 ‘O’ 组成，捕获所有被围绕的区域（将 ‘O’ 转变为 ‘X’）。

解析

从边界的 O 开始 DFS 标记为安全，剩余的 O 就是被包围的。

var solve = function (board) {
  const m = board.length, n = board[0].length;
  function dfs(i, j) {
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== 'O') return;
    board[i][j] = '#';
    dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1);
  }
  for (let i = 0; i < m; i++) { dfs(i, 0); dfs(i, n - 1); }
  for (let j = 0; j < n; j++) { dfs(0, j); dfs(m - 1, j); }
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      board[i][j] = board[i][j] === '#' ? 'O' : 'X';
};