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.length
• n == board[i].length
• 1 <= m, n <= 200
• board[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
    }
}