Leetcode - surrounded-regions

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[0].length == 0
    queue = []
    for i in 0..board.length-1
        [0, board[0].length-1].each do |j|
            queue << [i, j] if board[i][j] == "O"
        end
    end
    for j in 0..board[0].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[0].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[0].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[0]
            y = position[1]
           
            board[x][y] = "Y" if board[x][y] == "O"
            directions.each do |d|
                new_x = x + d[0]
                new_y = y + d[1]
                if new_x >= 0 && new_y >= 0 && new_x < board.length && new_y < board[0].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]) == 0{
        return
    }
    queue := [][]int{}
    for i := 0; i < len(board); i++ {
        if board[i][0] == 'O' {
            queue = append(queue, []int{i, 0})
        }
        if board[i][len(board[0])-1] == 'O' {
            queue = append(queue, []int{i, len(board[0])-1})
        }
    }
    for j := 0; j < len(board[0])-1; j++ {
        if board[0][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[0]); j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X'
            }
        }
    }
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); 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[0]
            y := position[1]
            if board[x][y] == 'O' {
                board[x][y] = 'Y'
            }
            for _, d := range directions {
                newX := x + d[0]
                newY := y + d[1]
                if newX >= 0 && newY >= 0 && newX < len(board) && newY < len(board[0]) {
                    if board[newX][newY] == 'O' {
                        queue = append(queue, []int{newX, newY})
                    }
                }
            }
        }
        queue = queue[size:]
    }
    return board
}

• 相关文章
• 全局相关文章