[LintCode] Surrounded Regions

Labradors 發(fā)布于2019-08-14 15:11 / 3115人閱讀

摘要：先用處理左右邊界上的換成再用處理上下邊界除去四角的換成把剩下的沒有被處理過，也就是被包圍的置為把所有暫時(shí)置為的不被包圍的換回如當(dāng)前字符的坐標(biāo)越界不是，返回是的都置為，然后迭代其上下左右各點(diǎn)

Problem

Given a 2D board containing "X" and "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 capture all regions surrounded by "X", the board should be:

X X X X
X X X X
X X X X
X O X X

Solution

public class Solution {
    public void surroundedRegions(char[][] board) {
        // Write your code here
        if (board == null || board.length < 2 || board[0].length < 2) return;
        int m = board.length;
        int n = board[0].length;
        //先用bfs處理左右邊界上的"O"(換成"#")
        for (int i = 0; i < m; i++) {
            if (board[i][0] == "O") {
                bfs(board, i, 0);
            }
            if (board[i][n-1] == "O") {
                bfs(board, i, n-1);
            }
        }
        //再用bfs處理上下邊界（除去四角）的"O"(換成"#")
        for (int i = 1; i < n-1; i++) {
            if (board[0][i] == "O") {
                bfs(board, 0, i);
            }
            if (board[m-1][i] == "O") {
                bfs(board, m-1, i);
            }
        }
        //把剩下的沒有被處理過，也就是被包圍的"O"置為"X"
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == "O") {
                    board[i][j] = "X";
                }
            }
        }
        //把所有暫時(shí)置為"#"的不被包圍的"O"換回"O"
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == "#") {
                    board[i][j] = "O";
                }
            }
        }
    }
    public void bfs(char[][] board, int row, int col) {
        //如當(dāng)前字符的坐標(biāo)越界or不是"O"，返回
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != "O") {
            return;
        }
        //是"O"的都置為"#"，然后迭代其上下左右各點(diǎn)
        board[row][col] = "#";
        bfs(board, row-1, col);
        bfs(board, row+1, col);
        bfs(board, row, col-1);
        bfs(board, row, col+1);
    }
}