leetcode 130被围绕的区域

思路

一个区域不能被围绕是这个区域有部分在边界

可以循环边界，找边界的区域（利用深搜），这些都不能被围绕，其余的，能被围绕，应该从"O"变为”X“

代码

static boolean[][] hasGo;//记录是否走过
    static int[][] to = {{0,1},{1,0},{-1,0},{0,-1}};
    public void solve(char[][] board) {
        hasGo = new boolean[board.length][board[0].length];
        for (int i = 0;i<board.length;i++){
            for (int j = 0; j<board[0].length;j++){
                //边界
                if (i==0||j==0|| i == board.length-1||j == board[0].length-1){//找边界
                   if (hasGo[i][j] == false && board[i][j] == 'O'){//没被走过且是可以走的
                       dfs(i,j,board);
                   }
                }
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O' && hasGo[i][j] == false){//是0，且从边界走不到
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void dfs(int i, int j, char[][] board) {
        hasGo[i][j] = true;// 这个点走过了
        for (int k = 0;k<4;k++){
            int ii = i + to[k][0];
            int jj = j + to[k][1];
            if (ii>=0 && ii<board.length&&jj>=0&&jj<board[0].length){
                if (hasGo[ii][jj] == false&& board[ii][jj] == '0'){
                    dfs(ii,jj,board);
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

注意

字符分别是大写的X和大写的O，我把O当成了0