 Time Flying  ### 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 - 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 坐标位于边界而且 boardm 为 'O'
3. boardm 为 '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.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], n + direction[i], 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 四周的值都不合理, 且 boradm === 'O', 则要让 boardm = '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.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], n + direction[i], used)
}
}``````

79、200