130. Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example:

[['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']]

X X X X
X O O X
X X O X
X O X X

X X X X
X O O X
X X O X
X - X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Example:

var test = [["O","O","O"],["O","O","O"],["O","O","O"]]

O O O
O O O
O O O

After running your function, the board should be:

O O O
O O O
O O O

Analyze

• 分析终止迭代(不合法)的条件
  1. m, n 坐标已经使用过;
  2. m, n 坐标位于边界而且 board[m][n] 为 'O'
  3. board[m][n] 为 'X'

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {
  const used = []
  for (let m = 0; m < board.length; m++) {
    for (let n = 0; n < board[m].length; n++) {
      if (used.indexOf(`${m},${n}`) === -1) {
        recursive(board, m, n, used)
      }
    }
  }
  return board
};

var direction = [[1, 0], [0, 1], [-1, 0], [0, -1]] // 下、右、上、左

// m: row; n: column
var isValid = (board, m, n, used) => {
  if (!board[m] || !board[m][n]) return false
  const notUsed = used.indexOf(`${m},${n}`) === -1
  used.push(`${m},${n}`)
  return notUsed
}

// judge if it is in board
var isInBorder = (board, m, n) => m === 0 || n === 0 || m === board.length - 1 || n === board[0].length - 1

var recursive = function(board, m, n, used) {
  // end condition.
  if (!isValid(board, m, n, used) || (isInBorder(board, m, n) && board[m][n] === 'O') || board[m][n] === 'X') {
    return false
  }
  for (let i = 0; i < direction.length; i++) {
    const tag = recursive(board, m + direction[i][0], n + direction[i][1], used)
    // recursive to set value
    if (tag && board[m][n] === 'O') {
      board[m][n] = 'X'
    }
    // 若不在边界的坐标 m,n 四周的值都不合理, 且 borad[m][n] === 'O', 则要让 board[m][n] = 'X'
    // todo: board[m][n - 1] === 'O'
    if (i === 3 && !isInBorder(board, m, n) && board[m][n] === 'O') {
      board[m][n] = 'X'
    }
  }
  return true
}

「若不在边界的坐标 m,n 四周的值都不合理, 且 borad[m][n] === 'O', 则要让 board[m][n] = 'X'」, 这个条件在如下测试用例面前是过不去的砍👀

O O O
O O O
O O O

观察评论区调整了下思路:

1. 将边界的 O 以及与其相连的 O 标记为 _。
2. 遍历节点
   1. 将剩余的 O 全部替换为 X。
   2. 将全部的 _ 替换为 O。

点子比行动更重要！

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {
  const used = []
  for (let m = 0; m < board.length; m++) {
    for (let n = 0; n < board[m].length; n++) {
      if (isInBorder(m, n, board) && board[m][n] === 'O') {
        replaceWith_(board, m, n, used)
      }
    }
  }

  for (let m = 0; m < board.length; m++) {
    for (let n = 0; n < board[m].length; n++) {
      if (board[m][n] === 'O') {
        board[m][n] = 'X'
      }
      if (board[m][n] === '_') {
        board[m][n] = 'O'
      }
    }
  }
  return board
};

// judge if it is in board
var isInBorder = (m, n, board) => m === 0 || n === 0 || m === board.length - 1 || n === board[0].length - 1

var isValid = (board, m, n, used) => {
  if (!board[m] || !board[m][n]) return false
  const notUsed = used.indexOf(`${m},${n}`) === -1
  used.push(`${m},${n}`)
  return notUsed
}

var direction = [[1, 0], [0, 1], [-1, 0], [0, -1]] // 下、右、上、左

var replaceWith_ = (board, m, n, used) => {
  if (!isValid(board, m, n, used) || board[m][n] === 'X') return
  if (board[m][n] === 'O') {
    board[m][n] = '_'
  }

  for (let i = 0; i < direction.length; i++) {
    replaceWith_(board, m + direction[i][0], n + direction[i][1], used)
  }
}

Sister Title

79、200