# DFS&BFS - 130. Surrounded Regions

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

``````

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.

go：

``````/*func solve(board [][]byte)  {

if board == nil || len(board) == 0 || len(board[0]) == 0 {
return
}

row, col := len(board), len(board[0])
var visited = make([][]bool, row)
for i := range visited {
visited[i] = make([]bool, col)
}

// 1.处理边界
for j := 0; j < col; j++ {
if board[0][j] == 'O' {
dfs(&board, 0, j, row, col, &visited, false)
}
if board[row-1][j] == 'O' {
dfs(&board, row -1, j, row, col, &visited, false)
}
}
for i := 0; i < row; i++ {
if board[i][0] == 'O' {
dfs(&board, i, 0, row, col, &visited, false)
}

if board[i][col-1] == 'O' {
dfs(&board, i, col - 1, row, col, &visited, false)
}
}

// 2. 常规dfs翻转剩下所有被包围的O

for i := 1; i < row; i++ {
for j := 1; j < col; j++ {
if board[i][j] == 'O' {
dfs(&board, i, j, row, col, &visited, true)
}
}
}
}

var dirs = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func dfs(board *[][]byte, i, j int, row, col int, visited *[][]bool, flip bool) {
if i < 0 || i >= row || j < 0 || j >= col || (*visited)[i][j] || (*board)[i][j] == 'X'{
return
}

if flip {
(*board)[i][j] = 'X'
}
(*visited)[i][j] = true

for _, dir := range dirs {
dfs(board, i + dir[0], j + dir[1], row, col, visited, flip)
}
}*/

func solve(board [][]byte)  {
if len(board) == 0 || len(board[0]) == 0 {
return
}

// 将与边界相邻的位置做标记
for i := 0; i < len(board); i++ {
if board[i][0] == 'O' {
dfs(board, i, 0)
}
if board[i][len(board[0])-1] == 'O' {
dfs(board, i, len(board[0])-1)
}
}

for i := 0; i < len(board[0]); i++ {
if board[0][i] == 'O' {
dfs(board, 0, i)
}
if board[len(board)-1][i] == 'O' {
dfs(board, len(board)-1, i)
}
}

// 将所有标记的位置重置为 'O', 并将没有设置标记的位置设为 'X'
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if board[i][j] == '*' {
board[i][j] = 'O'
} else if board[i][j] == 'O' {
board[i][j] = 'X'
}
}
}
}

func dfs(board [][]byte, i, j int) {
if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] != 'O' {
return
}

// 设置标记
board[i][j] = '*'

// 向四个方向移动
dfs(board, i+1, j)
dfs(board, i-1, j)
dfs(board, i, j+1)
dfs(board, i, j-1)
}
``````

Nothing just happens, it's all part of a plan.