surrounded-regions

56 阅读 0 评论 37 点赞

我是靠谱客的博主温柔外套，最近开发中收集的这篇文章主要介绍surrounded-regions，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.题目：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 .
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

2.分析思路：
①边界上的’O’予以保留
②与边界上的’O’相连的’O’予以保留
③其余’O’变成’X’
题目给出的‘X’，’O’信息用一个二维数组board保存。此外，我们可以创建一个二维状态数组state,用于表示board数组中相应位置为’X’还是为’O’。如state[i][j]为true,则相应的board[i][j]为’O’;state[i][j]为false,则相应的board[i][j]为’X’;

3.代码实现：

public class Solution {
    public void solve(char[][] board) {
        if(board==null || board.length==0 || board[0].length==0) return ;//如果board数组为空则直接结束
        int m=board.length;
        int n=board[0].length;
        if(m==1 || n==1) return ;//如果board是一位数组，则直接返回
        boolean [][] state=new boolean [m][n];//状态数组，若state[i][j]为true则board[i][j]处应该为'O'，否则为'X'
        //初始化边界的状态
        for(int i=0;i<n;i++){
            if(board[0][i]=='O'){
                state[0][i]=true;
                judge(board,state,0,i);
            } 
            if(board[m-1][i]=='O'){
                state[m-1][i]=true;
                judge(board,state,m-1,i);
            } 
        }
        for(int i=1;i<m-1;i++){
            if(board[i][0]=='O'){
                state[i][0]=true;
                judge(board,state,i,0);
            } 
            if(board[i][n-1]=='O'){
                state[i][n-1]=true;
                judge(board,state,i,n-1);
            } 
        }
        /**该段程序可加可不加
        //设置状态数组的值
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(state[i][j]) judge(board,state,i,j);
            }
        }
        */
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!state[i][j] && board[i][j]=='O') board[i][j]='X';
            }
        }
    }
    public void judge(char [][] board,boolean [][] state,int i,int j){
        if(i-1>0 && board[i-1][j]=='O' && !state[i-1][j]) {//在判断语句中必须加上!state[i-1][j]，否者复杂度过大
            state[i-1][j]=true;
            judge(board,state,i-1,j);
        }
        if(i+1<board.length-1 && board[i+1][j]=='O' && !state[i+1][j]) {//在判断语句中必须加上!state[i+1][j]，否者复杂度过大
            state[i+1][j]=true;
            judge(board,state,i+1,j);
        }
        if(j-1>0 && board[i][j-1]=='O' && !state[i][j-1]){//在判断语句中必须加上!state[i][j-1]，否者复杂度过大
            state[i][j-1]=true;
            judge(board,state,i,j-1);
        } 
        if(j+1<board[0].length-1 && board[i][j+1]=='O' && !state[i][j+1]){//在判断语句中必须加上!state[i][j+1]，否者复杂度过大
            state[i][j+1]=true;
            judge(board,state,i,j+1);
        }
    }
}