转载

130. 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

Explanation:

Surrounded regions shouldn’t 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.

难度：medium

题目：给定由X和O组成的二维表格，找出所有由X包含的区域并将O转成X.

思路：遍历二维表格四边将以0开始的元素延伸到整个二维表并将其值置成非X非O（如Ｂ）字符用以区分与其它元素。然后遍历整个二维表将除Ｂ以外的所有元素设为X, Ｂ元素恢复为O

Runtime: 4 ms, faster than 96.33% of Java online submissions for Surrounded Regions.

Memory Usage: 40.7 MB, less than 100.00% of Java online submissions for Surrounded Regions.

class Solution {
    public void solve(char[][] board) {
        if (null == board || board.length <= 1 || board[0].length <= 1) {
            return;
        }
        
        int m = board.length, n = board[0].length;
        for (int i: Arrays.asList(0, m - 1)) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    color(board, i, j);
                }
            }
        }
        for (int i: Arrays.asList(0, n - 1)) {
            for (int j = 0; j < m; j++) {
                if (board[j][i] == 'O') {
                    color(board, j, i);
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O' || board[i][j] == 'X') {
                    board[i][j] = 'X';
                } else {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    private void color(char[][] board, int i, int j) {
        if (i < 0 || i >= board.length 
            || j < 0 || j >= board[i].length 
            || board[i][j] != 'O') {
            return;
        }
        
        board[i][j] = 'B';
        color(board, i + 1, j);
        color(board, i - 1, j);
        color(board, i, j + 1);
        color(board, i, j - 1);
    }
}

原文 https://segmentfault.com/a/1190000018176937

正文到此结束