Contents

# Problem

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 1

 ``````1 2 3 4 `````` ``````X X X X X O O X X X O X X O X X ``````

After running your function, the board should be:

 ``````1 2 3 4 `````` ``````X X X X X X X X X X X X X O X X ``````

# Solution

## DFS

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 `````` `````` func solve(board [][]byte) { a := make([][]int, len(board)) for idx := range board { a[idx] = make([]int, len(board[idx])) } for idx := range board { if idx == 0 || idx == len(board)-1 { for jdx := range board[idx] { if board[idx][jdx] == 'O' && a[idx][jdx] == 0 { visit(board, a, idx, jdx) } } } else { jdx := 0 if board[idx][jdx] == 'O' && a[idx][jdx] == 0 { visit(board, a, idx, jdx) } jdx = len(board[idx]) - 1 if board[idx][jdx] == 'O' && a[idx][jdx] == 0 { visit(board, a, idx, jdx) } } } for idx := range board { for jdx := range board[idx] { if a[idx][jdx] != 1 { board[idx][jdx] = 'X' } } } } func visit(board [][]byte, a [][]int, i, j int) { a[i][j] = 1 if j+1 < len(board[i]) && board[i][j+1] == 'O' && a[i][j+1] == 0 { visit(board, a, i, j+1) } if j-1 >= 0 && board[i][j-1] == 'O' && a[i][j-1] == 0 { visit(board, a, i, j-1) } if i+1 < len(board) && board[i+1][j] == 'O' && a[i+1][j] == 0 { visit(board, a, i+1, j) } if i-1 >= 0 && board[i-1][j] == 'O' && a[i-1][j] == 0 { visit(board, a, i-1, j) } } ``````