# Leetcode - surrounded-regions

violet posted @ Mar 11, 2020 06:36:33 AM in 算法 with tags ruby Algorithm BFS Golang , 382 阅读

https://leetcode.com/problems/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
```

Firstly what I was thinking about is finding all `X` which surround the `O`. I found that it's very difficult to tackle things done cause `X` may not be tracked either by bfs and dfs. I learned another way from the discussion here

It should find all `O` from the boarder and use bfs or dfs to track all` O` surrounding boarder `O`. Mark them as "`Y`". And then iterate in the board, mark all `O` into `X`. Mark all `Y` to `O` in the end.

```# @param {Character[][]} board
# @return {Void} Do not return anything, modify board in-place instead.
def solve(board)
return if board.length == 0 || board.length == 0
queue = []
for i in 0..board.length-1
[0, board.length-1].each do |j|
queue << [i, j] if board[i][j] == "O"
end
end
for j in 0..board.length-1
[0, board.length-1].each do |i|
queue << [i, j] if board[i][j] == "O"
end
end
mark_O(board, queue)
for i in 0..board.length-1
for j in 0..board.length-1
board[i][j] = "X" if board[i][j] == "O"
end
end
for i in 0..board.length-1
for j in 0..board.length-1
board[i][j] = "O" if board[i][j] == "Y"
end
end
end

def mark_O(board, queue)
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
while queue.length != 0
size = queue.length
for k in 0..size-1
position = queue[k]
x = position
y = position

board[x][y] = "Y" if board[x][y] == "O"
directions.each do |d|
new_x = x + d
new_y = y + d
if new_x >= 0 && new_y >= 0 && new_x < board.length && new_y < board.length
queue << [new_x, new_y] if board[new_x][new_y] == "O"
end
end
end
queue = queue[size..-1]
end
end```
```func solve(board [][]byte)  {
if len(board) == 0 || len(board) == 0{
return
}
queue := [][]int{}
for i := 0; i < len(board); i++ {
if board[i] == 'O' {
queue = append(queue, []int{i, 0})
}
if board[i][len(board)-1] == 'O' {
queue = append(queue, []int{i, len(board)-1})
}
}
for j := 0; j < len(board)-1; j++ {
if board[j] == 'O' {
queue = append(queue, []int{0, j})
}
if board[len(board)-1][j] == 'O' {
queue = append(queue, []int{len(board)-1, j})
}
}
board = mark(board, queue)
for i := 0; i < len(board); i++ {
for j := 0; j < len(board); j++ {
if board[i][j] == 'O' {
board[i][j] = 'X'
}
}
}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board); j++ {
if board[i][j] == 'Y' {
board[i][j] = 'O'
}
}
}
}

func mark(board [][]byte, queue [][]int) [][]byte {
directions := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
for len(queue) != 0 {
size := len(queue)
for k := 0; k < size; k++{
position := queue[k]
x := position
y := position
if board[x][y] == 'O' {
board[x][y] = 'Y'
}
for _, d := range directions {
newX := x + d
newY := y + d
if newX >= 0 && newY >= 0 && newX < len(board) && newY < len(board) {
if board[newX][newY] == 'O' {
queue = append(queue, []int{newX, newY})
}
}
}
}
queue = queue[size:]
}
return board
}``` (输入验证码)
or Ctrl+Enter