# Surrounded Regions Leetcode

#1

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.

#2

Start with the first/last row and first/last columns, mark all `O` as some character, in the below I program we use `#`. This basically takes out all `O`'s which are supposed to be preserved. Now do a traversal, mark all `#` as `O` rest of them as `X`.

``````func solve(board [][]byte)  {
if (len(board)<=1 || len(board[0])==1) { return }
rows, cols := len(board), len(board[0])
for i:=0;i<len(board[0]);i++{
if board[0][i]=='O'{
dfs(board, 0, i)
}
if board[rows-1][i]=='O'{
dfs(board, rows-1, i)
}
}

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

for i:=0;i<len(board);i++{
for j:=0;j<len(board[i]);j++{
if board[i][j] == '#'{
board[i][j] = 'O'
} else {
board[i][j] = 'X'
}
}
}
}

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

func dfs(board [][]byte, i, j int) {
if(i<0 || j<0 || i>len(board)-1 || j>len(board[0])-1 || board[i][j]!='O'){ return }
board[i][j] = '#'
for a:=0;a<len(xy);a++{
ax, ay := i+xy[a][0], j+xy[a][1]
dfs(board, ax , ay)
}
}
``````