130. Surrounded Regions

[Tcdian]

130. Surrounded Regions

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

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

Explanation

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {
    const queue = findEdgeO(board);
    dfs();
    recover();

    function findEdgeO(board) {
        const queue = [];
        for (let i = 0; i < board.length; i++) {
            for (let j = 0; j < board[0].length; j++) {
                if (
                    board[i][j] === 'O'
                        && (i === 0 || i === board.length - 1 || j === 0 || j === board[0].length - 1)
                ) {
                    queue.push([i, j]);
                }
            }
        }
        return queue;
    }

    function dfs() {
        const direction = [-1, 0, 1, 0, -1];
        while(queue.length !== 0) {
            const [x, y] = queue.pop();
            board[x][y] = 'V';
            for (let d = 0; d < 4; d++) {
                const directionX = direction[d] + x;
                const directionY = direction[d + 1] + y;
                if (
                    directionX >= 0 && directionX < board.length
                        && directionY >= 0 && directionY < board[0].length
                        && board[directionX][directionY] === 'O'
                ) {
                    queue.push([directionX, directionY]);
                }
            }
        }
    }

    function recover() {
        for (let i = 0; i < board.length; i++) {
            for (let j = 0; j < board[0].length; j++) {
                if (board[i][j] === 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] === 'V') {
                    board[i][j] = 'O';
                }
            }
        }
    }
};

• TypeScript Solution

/**
 Do not return anything, modify board in-place instead.
 */
function solve(board: string[][]): void {
    const queue = findEdgeO(board);
    dfs();
    recover();

    function findEdgeO(board: string[][]) {
        const queue: [number, number][] = [];
        for (let i = 0; i < board.length; i++) {
            for (let j = 0; j < board[0].length; j++) {
                if (
                    board[i][j] === 'O'
                        && (i === 0 || i === board.length - 1 || j === 0 || j === board[0].length - 1)
                ) {
                    queue.push([i, j]);
                }
            }
        }
        return queue;
    }

    function dfs() {
        const direction = [-1, 0, 1, 0, -1];
        while(queue.length !== 0) {
            const [x, y] = queue.pop() as [number, number];
            board[x][y] = 'V';
            for (let d = 0; d < 4; d++) {
                const directionX = direction[d] + x;
                const directionY = direction[d + 1] + y;
                if (
                    directionX >= 0 && directionX < board.length
                        && directionY >= 0 && directionY < board[0].length
                        && board[directionX][directionY] === 'O'
                ) {
                    queue.push([directionX, directionY]);
                }
            }
        }
    }

    function recover() {
        for (let i = 0; i < board.length; i++) {
            for (let j = 0; j < board[0].length; j++) {
                if (board[i][j] === 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] === 'V') {
                    board[i][j] = 'O';
                }
            }
        }
    }
};