# 130. Surrounded Regions

## 題目敘述

Given an `m x n` matrix `board` containing `'X'` and `'O'`, capture all regions that are 4-directionally surrounded by `'X'`.

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

Example 1:

``````Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not 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 2:

``````Input: board = [["X"]]
Output: [["X"]]
``````

Constraints:

• `m == board.length`
• `n == board[i].length`
• `1 <= m, n <= 200`
• `board[i][j]` is `'X'` or `'O'`.

## 解法解析

### 解法範例

#### DFS

``````func solve(board [][]byte) {
m := len(board)
n := len(board[0])

if m == 1 || n == 1 {
return
}

idx := []int{0, m - 1}
for _, k := range idx {
for i := range board[k] {
if board[k][i] == 'O' {
dfs(board, m, n, k, i)
}
}
}
idx = []int{0, n - 1}
for _, k := range idx {
for i := range board {
if board[i][k] == 'O' {
dfs(board, m, n, i, k)
}
}
}

for i := 0; i < m; i += 1 {
for j := 0; j < n; j += 1 {
if board[i][j] == '.' {
board[i][j] = 'O'
} else if board[i][j] == 'O' {
board[i][j] = 'X'
}
}
}
}

func dfs(board [][]byte, rows, cols, r, c int) {
board[r][c] = '.'

dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
for i := range dirs {
rr := r + dirs[i][0]
cc := c + dirs[i][1]
if rr < 0 || rr >= rows || cc < 0 || cc >= cols || board[rr][cc] != 'O' {
continue
}
dfs(board, rows, cols, rr, cc)
}
}
``````
##### BFS
``````type coordinate struct {
x, y int
}

func bfs(c coordinate, board [][]byte) {
var q []coordinate
board[c.x][c.y] = '1'
q = append(q, c)

for len(q) != 0 {
e := q[0]
q = q[1:]
for _, v := range []coordinate{
{e.x - 1, e.y},
{e.x + 1, e.y},
{e.x, e.y - 1},
{e.x, e.y + 1}} {
if v.x >= 0 && v.x < len(board) && v.y >= 0 && v.y < len(board[v.x]) && board[v.x][v.y] == 'O' {
board[v.x][v.y] = '1'
q = append(q, v)
}
}
}
}

func solve(board [][]byte) {
for i := 0; i < len(board); i++ {
if i == 0 || i == (len(board)-1) {
for j := 0; j < len(board[i]); j++ {
if board[i][j] == 'O' {
bfs(coordinate{i, j}, board)
}
}
} else {
for _, j := range []int{0, len(board[i]) - 1} {
if board[i][j] == 'O' {
bfs(coordinate{i, j}, board)
}
}
}
}

for i := 0; i < len(board); i++ {
for j := 0; j < len(board[i]); j++ {
switch board[i][j] {
case 'O':
board[i][j] = 'X'
case '1':
board[i][j] = 'O'
}
}
}
}
``````

#### JavaScript

##### DFS
``````/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function (board) {
const rows = board.length;
const cols = board[0].length;

const dfs = (row, col) => {
if (row < 0 || col < 0 || row == rows || col == cols) return;
if (board[row][col] != 'O') return;
board[row][col] = 'T';
dfs(row + 1, col);
dfs(row - 1, col);
dfs(row, col + 1);
dfs(row, col - 1);
};

for (let row = 0; row < rows; ++row) {
if (board[row][0] == 'O') {
dfs(row, 0);
}

if (board[row][cols - 1] == 'O') {
dfs(row, cols - 1);
}
}

for (let col = 0; col < cols; ++col) {
if (board[0][col] == 'O') {
dfs(0, col);
}

if (board[rows - 1][col] == 'O') {
dfs(rows - 1, col);
}
}

for (let row = 0; row < rows; ++row) {
for (let col = 0; col < cols; ++col) {
if (board[row][col] == 'O') {
board[row][col] = 'X';
} else if (board[row][col] == 'T') {
board[row][col] = 'O';
}
}
}
};
``````
##### BFS
``````/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function (board) {
const N = board.length;
if (!N) return;
const M = board[0].length;
const visit = Array(N)
.fill(null)
.map((i) => Array(M).fill(false));
const dx = [1, -1, 0, 0],
dy = [0, 0, 1, -1];

function BFS(i, j) {
visit[i][j] = true;
const queue = [[i, j]];
while (queue.length) {
let [x, y] = queue.shift();
for (let d = 0; d < 4; d++) {
let nx = x + dx[d],
ny = y + dy[d];
if (-1 < nx && nx < N && -1 < ny && ny < M) {
if (!visit[nx][ny] && board[nx][ny] == 'O') {
visit[nx][ny] = true;
queue.push([nx, ny]);
}
}
}
}
}

for (let i = 0; i < N; i++) {
if (!visit[i][0] && board[i][0] == 'O') BFS(i, 0);
if (!visit[i][M - 1] && board[i][M - 1] == 'O') BFS(i, M - 1);
}
for (let j = 1; j < M - 1; j++) {
if (!visit[0][j] && board[0][j] == 'O') BFS(0, j);
if (!visit[N - 1][j] && board[N - 1][j] == 'O') BFS(N - 1, j);
}
for (let i = 1; i < N - 1; i++) {
for (let j = 1; j < M - 1; j++) {
if (!visit[i][j] && board[i][j] == 'O') board[i][j] = 'X';
}
}
};
``````

#### Kotlin

##### DFS
``````class Solution {
fun solve(board: Array<CharArray>): Unit {
if (board.isEmpty() || board[0].isEmpty()) return

val m = board.size
val n = board[0].size

fun dfs(x: Int, y: Int, symbol: Char) {
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') return

board[x][y] = symbol

dfs(x + 1, y, symbol)
dfs(x - 1, y, symbol)
dfs(x, y + 1, symbol)
dfs(x, y - 1, symbol)
}

for (j in 0..n - 2) dfs(0, j, '#')
for (i in 0..m - 2) dfs(i, n - 1, '#')
for (j in n - 1 downTo 1) dfs(m - 1, j, '#')
for (i in m - 1 downTo 1) dfs(i, 0, '#')

for (i in 1..m - 2) {
for (j in 1..n - 2) {
dfs(i, j, 'X')
}
}

for (i in 0..m - 1) {
for (j in 0..n - 1) {
if (board[i][j] == '#') {
board[i][j] = 'O'
}
}
}
}
}
``````

#### PHP

``````
``````

#### Python

##### DFS
``````class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return

self.ROWS = len(board)
self.COLS = len(board[0])

# Step 1). retrieve all border cells
# from itertools import product
# borders = list(product(range(self.ROWS), [0, self.COLS-1])) \
#     + list(product([0, self.ROWS-1], range(self.COLS)))
borders = []
for i in range(self.ROWS):
for j in range(self.COLS):
borders.append((i, j))

# Step 2). mark the "escaped" cells, with any placeholder, e.g. 'E'
for row, col in borders:
self.DFS(board, row, col)

# Step 3). flip the captured cells ('O'->'X') and the escaped one ('E'->'O')
for r in range(self.ROWS):
for c in range(self.COLS):
if board[r][c] == 'O':
board[r][c] = 'X'  # captured
elif board[r][c] == 'E':
board[r][c] = 'O'  # escaped

def DFS(self, board, row, col):
if board[row][col] != 'O':
return
board[row][col] = 'E'
if col < self.COLS-1:
self.DFS(board, row, col+1)
if row < self.ROWS-1:
self.DFS(board, row+1, col)
if col > 0:
self.DFS(board, row, col-1)
if row > 0:
self.DFS(board, row-1, col)
``````
##### BFS
``````class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return

self.ROWS = len(board)
self.COLS = len(board[0])

# Step 1). retrieve all border cells
from itertools import product
borders = list(product(range(self.ROWS), [0, self.COLS-1])) \
+ list(product([0, self.ROWS-1], range(self.COLS)))

# Step 2). mark the "escaped" cells, with any placeholder, e.g. 'E'
for row, col in borders:
#self.DFS(board, row, col)
self.BFS(board, row, col)

# Step 3). flip the captured cells ('O'->'X') and the escaped one ('E'->'O')
for r in range(self.ROWS):
for c in range(self.COLS):
if board[r][c] == 'O':
board[r][c] = 'X'  # captured
elif board[r][c] == 'E':
board[r][c] = 'O'  # escaped

def BFS(self, board, row, col):
from collections import deque
queue = deque([(row, col)])
while queue:
(row, col) = queue.popleft()
if board[row][col] != 'O':
continue
# mark this cell as escaped
board[row][col] = 'E'
# check its neighbor cells
if col < self.COLS-1:
queue.append((row, col+1))
if row < self.ROWS-1:
queue.append((row+1, col))
if col > 0:
queue.append((row, col-1))
if row > 0:
queue.append((row-1, col))
``````

#### Rust

``````
``````

#### Swift

##### DFS
``````class Solution {
func solve(_ board: inout [[Character]]) {
guard let column = board.first?.count else {
return
}

let row = board.count

var edges = [Pair<Int>]()

for i in 0..<row {
edges.append(Pair<Int>(row: i, column: 0))
edges.append(Pair<Int>(row: i, column: column - 1))
}
for j in 0..<column {
edges.append(Pair<Int>(row: 0, column: j))
edges.append(Pair<Int>(row: row - 1, column: j))
}
// Go through the edges and find "O" and apply dfs to all neighbours
for pair in edges {
dfsMe(&board, pair.row, pair.column)
}

// "W" - are not surrounded, so we need to make them "O" again
// "O" - surrounded ones
for i in 0..<row {
for j in 0..<column {
if board[i][j] == "W" {
board[i][j] = "O"
} else if board[i][j] == "O" {
board[i][j] = "X"
}
}
}
}

func dfsMe(_ board: inout [[Character]], _ i: Int, _ j: Int) {
if j < 0 || i < 0 || board.first!.count <= j || board.count <= i || board[i][j] == "X" || board[i][j] == "W" {
return
}

board[i][j] = "W"

dfsMe(&board, i + 1, j)
dfsMe(&board, i - 1, j)
dfsMe(&board, i, j + 1)
dfsMe(&board, i, j - 1)
}

struct Pair<Value> {
var row: Value
var column: Value
}
}
``````