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.
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 | # @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 endenddef 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] endend |
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 56 57 58 59 60 61 62 63 | 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} |
评论 (0)
