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.

For 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

思路: 用的BFS来做的, 先从边界条件寻找’O’, 把边界条件的O用BFS来找到的都不满足被X包围的条件,替换为’Y’,然后剩下图里的O 都满足被X包围的条件,直接替换为X; 最后再把边界的‘Y’替换回‘0’.

public class Solution {
    int[] xDir = new int[]{-1, 0, 1, 0};
    int[] yDir = new int[]{0, 1, 0, -1};
    public void solve(char[][] board) {
        if (board == null || board[0] == null 
         || board.length < 3 || board[0].length < 3 ) return;
        fillBoards(board, 'O', 'Y');
        solve(board, 'O', 'X');
        fillBoards(board, 'Y', 'O');
    }

    public void solve(char[][] board, char target, char c) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == target) {
                    board[i][j] = c;
                }
            }
        }
    }

    public void fill(char[][] board, int x, int y, char target, char c) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != target) return;
        board[x][y] = c;
        for(int i = 0; i < 4; i++) {
            int newX = x + xDir[i];
            int newY = y + yDir[i];
            fill(board, newX, newY, target, c);
        }
    }

    public void fillBoards(char[][] board, char target, char c) {
        int row = board.length - 1;
        int col = board[0].length - 1;
        for (int i = 0; i <= row; i++) {
            if (board[i][0] == target) fill(board, i, 0, target, c);
            if (board[i][col] == target) fill(board, i, col, target,c);
        }

        for (int j = 0; j <= row; j++) {
            if (board[0][j] == target) fill(board, 0, j, target, c);
            if (board[row][j] == target) fill(board, row, j, target, c);
        }
    }


}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s