LeetCode Solution, Medium, 130. Surrounded Regions
Published
130. Surrounded Regions
題目敘述
Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
Example 1:
Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not 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.
Example 2:
Input: board = [["X"]]
Output: [["X"]]
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j]is'X'or'O'.
題目翻譯
這題簡單來說就是類似圍棋的規則，只要被 X 包圍的 O 就要替換成 X。主要不同的地方在於，圍棋的話在邊緣的 O 會被當作被包圍了。但是這邊在邊緣的話不算。所以解法可以得知，只有連接到邊緣的 O 不會被替換成 X。
解法解析
這題解法主要有兩個 DFS(Depth-First Search) 和 BFS(Breadth-First Search)。
DFS 主要從邊緣，一圈一圈的往裡面找有沒有連結的 O。
BFS 則是從邊緣，找到有在邊緣的 O 後，往其四周去找有沒有連結的 O。
解法範例
Go
DFS
func solve(board [][]byte) {
m := len(board)
n := len(board[0])
if m == 1 || n == 1 {
return
}
idx := []int{0, m - 1}
for _, k := range idx {
for i := range board[k] {
if board[k][i] == 'O' {
dfs(board, m, n, k, i)
}
}
}
idx = []int{0, n - 1}
for _, k := range idx {
for i := range board {
if board[i][k] == 'O' {
dfs(board, m, n, i, k)
}
}
}
for i := 0; i < m; i += 1 {
for j := 0; j < n; j += 1 {
if board[i][j] == '.' {
board[i][j] = 'O'
} else if board[i][j] == 'O' {
board[i][j] = 'X'
}
}
}
}
func dfs(board [][]byte, rows, cols, r, c int) {
board[r][c] = '.'
dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
for i := range dirs {
rr := r + dirs[i][0]
cc := c + dirs[i][1]
if rr < 0 || rr >= rows || cc < 0 || cc >= cols || board[rr][cc] != 'O' {
continue
}
dfs(board, rows, cols, rr, cc)
}
}
BFS
type coordinate struct {
x, y int
}
func bfs(c coordinate, board [][]byte) {
var q []coordinate
board[c.x][c.y] = '1'
q = append(q, c)
for len(q) != 0 {
e := q[0]
q = q[1:]
for _, v := range []coordinate{
{e.x - 1, e.y},
{e.x + 1, e.y},
{e.x, e.y - 1},
{e.x, e.y + 1}} {
if v.x >= 0 && v.x < len(board) && v.y >= 0 && v.y < len(board[v.x]) && board[v.x][v.y] == 'O' {
board[v.x][v.y] = '1'
q = append(q, v)
}
}
}
}
func solve(board [][]byte) {
for i := 0; i < len(board); i++ {
if i == 0 || i == (len(board)-1) {
for j := 0; j < len(board[i]); j++ {
if board[i][j] == 'O' {
bfs(coordinate{i, j}, board)
}
}
} else {
for _, j := range []int{0, len(board[i]) - 1} {
if board[i][j] == 'O' {
bfs(coordinate{i, j}, board)
}
}
}
}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[i]); j++ {
switch board[i][j] {
case 'O':
board[i][j] = 'X'
case '1':
board[i][j] = 'O'
}
}
}
}
JavaScript
DFS
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function (board) {
const rows = board.length;
const cols = board[0].length;
const dfs = (row, col) => {
if (row < 0 || col < 0 || row == rows || col == cols) return;
if (board[row][col] != 'O') return;
board[row][col] = 'T';
dfs(row + 1, col);
dfs(row - 1, col);
dfs(row, col + 1);
dfs(row, col - 1);
};
for (let row = 0; row < rows; ++row) {
if (board[row][0] == 'O') {
dfs(row, 0);
}
if (board[row][cols - 1] == 'O') {
dfs(row, cols - 1);
}
}
for (let col = 0; col < cols; ++col) {
if (board[0][col] == 'O') {
dfs(0, col);
}
if (board[rows - 1][col] == 'O') {
dfs(rows - 1, col);
}
}
for (let row = 0; row < rows; ++row) {
for (let col = 0; col < cols; ++col) {
if (board[row][col] == 'O') {
board[row][col] = 'X';
} else if (board[row][col] == 'T') {
board[row][col] = 'O';
}
}
}
};
BFS
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function (board) {
const N = board.length;
if (!N) return;
const M = board[0].length;
const visit = Array(N)
.fill(null)
.map((i) => Array(M).fill(false));
const dx = [1, -1, 0, 0],
dy = [0, 0, 1, -1];
function BFS(i, j) {
visit[i][j] = true;
const queue = [[i, j]];
while (queue.length) {
let [x, y] = queue.shift();
for (let d = 0; d < 4; d++) {
let nx = x + dx[d],
ny = y + dy[d];
if (-1 < nx && nx < N && -1 < ny && ny < M) {
if (!visit[nx][ny] && board[nx][ny] == 'O') {
visit[nx][ny] = true;
queue.push([nx, ny]);
}
}
}
}
}
for (let i = 0; i < N; i++) {
if (!visit[i][0] && board[i][0] == 'O') BFS(i, 0);
if (!visit[i][M - 1] && board[i][M - 1] == 'O') BFS(i, M - 1);
}
for (let j = 1; j < M - 1; j++) {
if (!visit[0][j] && board[0][j] == 'O') BFS(0, j);
if (!visit[N - 1][j] && board[N - 1][j] == 'O') BFS(N - 1, j);
}
for (let i = 1; i < N - 1; i++) {
for (let j = 1; j < M - 1; j++) {
if (!visit[i][j] && board[i][j] == 'O') board[i][j] = 'X';
}
}
};
Kotlin
DFS
class Solution {
fun solve(board: Array<CharArray>): Unit {
if (board.isEmpty() || board[0].isEmpty()) return
val m = board.size
val n = board[0].size
fun dfs(x: Int, y: Int, symbol: Char) {
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') return
board[x][y] = symbol
dfs(x + 1, y, symbol)
dfs(x - 1, y, symbol)
dfs(x, y + 1, symbol)
dfs(x, y - 1, symbol)
}
for (j in 0..n - 2) dfs(0, j, '#')
for (i in 0..m - 2) dfs(i, n - 1, '#')
for (j in n - 1 downTo 1) dfs(m - 1, j, '#')
for (i in m - 1 downTo 1) dfs(i, 0, '#')
for (i in 1..m - 2) {
for (j in 1..n - 2) {
dfs(i, j, 'X')
}
}
for (i in 0..m - 1) {
for (j in 0..n - 1) {
if (board[i][j] == '#') {
board[i][j] = 'O'
}
}
}
}
}
PHP
Python
DFS
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
self.ROWS = len(board)
self.COLS = len(board[0])
# Step 1). retrieve all border cells
# from itertools import product
# borders = list(product(range(self.ROWS), [0, self.COLS-1])) \
# + list(product([0, self.ROWS-1], range(self.COLS)))
borders = []
for i in range(self.ROWS):
for j in range(self.COLS):
borders.append((i, j))
# Step 2). mark the "escaped" cells, with any placeholder, e.g. 'E'
for row, col in borders:
self.DFS(board, row, col)
# Step 3). flip the captured cells ('O'->'X') and the escaped one ('E'->'O')
for r in range(self.ROWS):
for c in range(self.COLS):
if board[r][c] == 'O':
board[r][c] = 'X' # captured
elif board[r][c] == 'E':
board[r][c] = 'O' # escaped
def DFS(self, board, row, col):
if board[row][col] != 'O':
return
board[row][col] = 'E'
if col < self.COLS-1:
self.DFS(board, row, col+1)
if row < self.ROWS-1:
self.DFS(board, row+1, col)
if col > 0:
self.DFS(board, row, col-1)
if row > 0:
self.DFS(board, row-1, col)
BFS
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
self.ROWS = len(board)
self.COLS = len(board[0])
# Step 1). retrieve all border cells
from itertools import product
borders = list(product(range(self.ROWS), [0, self.COLS-1])) \
+ list(product([0, self.ROWS-1], range(self.COLS)))
# Step 2). mark the "escaped" cells, with any placeholder, e.g. 'E'
for row, col in borders:
#self.DFS(board, row, col)
self.BFS(board, row, col)
# Step 3). flip the captured cells ('O'->'X') and the escaped one ('E'->'O')
for r in range(self.ROWS):
for c in range(self.COLS):
if board[r][c] == 'O':
board[r][c] = 'X' # captured
elif board[r][c] == 'E':
board[r][c] = 'O' # escaped
def BFS(self, board, row, col):
from collections import deque
queue = deque([(row, col)])
while queue:
(row, col) = queue.popleft()
if board[row][col] != 'O':
continue
# mark this cell as escaped
board[row][col] = 'E'
# check its neighbor cells
if col < self.COLS-1:
queue.append((row, col+1))
if row < self.ROWS-1:
queue.append((row+1, col))
if col > 0:
queue.append((row, col-1))
if row > 0:
queue.append((row-1, col))
Rust
Swift
DFS
class Solution {
func solve(_ board: inout [[Character]]) {
guard let column = board.first?.count else {
return
}
let row = board.count
var edges = [Pair<Int>]()
// Add vertical edges
for i in 0..<row {
edges.append(Pair<Int>(row: i, column: 0))
edges.append(Pair<Int>(row: i, column: column - 1))
}
// Add horizontal edges
for j in 0..<column {
edges.append(Pair<Int>(row: 0, column: j))
edges.append(Pair<Int>(row: row - 1, column: j))
}
// Go through the edges and find "O" and apply dfs to all neighbours
for pair in edges {
dfsMe(&board, pair.row, pair.column)
}
// "W" - are not surrounded, so we need to make them "O" again
// "O" - surrounded ones
for i in 0..<row {
for j in 0..<column {
if board[i][j] == "W" {
board[i][j] = "O"
} else if board[i][j] == "O" {
board[i][j] = "X"
}
}
}
}
func dfsMe(_ board: inout [[Character]], _ i: Int, _ j: Int) {
if j < 0 || i < 0 || board.first!.count <= j || board.count <= i || board[i][j] == "X" || board[i][j] == "W" {
return
}
board[i][j] = "W"
dfsMe(&board, i + 1, j)
dfsMe(&board, i - 1, j)
dfsMe(&board, i, j + 1)
dfsMe(&board, i, j - 1)
}
struct Pair<Value> {
var row: Value
var column: Value
}
}