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

一刷:

  1. 在4条边上,如果有元素为'O', 则转为'1', 并且与它相临的'O'都转为'1'
  2. 将其他的'O'都转为'X'
  3. 将'1'都转为'O'
public class Solution {
    public void solve(char[][] board) {
        int row = board.length;
        if(row==0) return;
        int col = board[0].length;
        
        
        //flip the 0 in the edge and adjacent area to 1
        for(int i=0; i<row; i++){
            check(board, i, 0, row, col);//edge
            if(col>1) check(board, i, col-1, row, col);//edge
        }
        for(int j=0; j<col; j++){
            check(board, 0, j, row, col);//edge
            if(row>1) check(board, row-1, j, row, col);//edge
        }
        
        
        //flip all other 0 to x
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }
        
        //flip all 1 to 0
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(board[i][j] == '1') board[i][j] = 'O';
            }
        }
    }
    
    private void check(char[][] board, int i, int j, int row, int col){
        //flip the 0 in the edge to 1
        if(board[i][j] == 'O'){
            board[i][j] = '1';
            if(i>1) check(board, i-1, j, row, col);
            if(j>1) check(board, i, j-1, row, col);
            if(i+1<row) check(board, i+1, j, row, col);
            if(j+1<col) check(board, i, j+1, row, col);
        }
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容