🌕 🌕 130. 被围绕的区域

难度: 🌕 🌕

问题描述

---

解法

class Solution {
    public void solve(char[][] board) {
        // 思路：
        // 要找到哪些是被 X 环绕的 0
        // 即，哪些是不被 X 环绕的 0？ ==> 与边界的 0 相连的 0 就是不被环绕的
        // 找到边界的 0 ，以 该点向四个方向做深度优先搜索
        int row = board.length;
        int col = board[0].length;
        for(int i = 0; i < row; i ++) {
            if(board[i][0] == 'O') {
                mySol(board, row, col, i, 0);
            }
            if(board[i][col - 1] == 'O') {
                mySol(board, row, col, i, col - 1);
            }
        }
        for(int j = 0; j < col; j ++) {
            if(board[0][j] == 'O') {
                mySol(board, row, col, 0, j);
            }
            if(board[row - 1][j] == 'O') {
                mySol(board, row, col, row - 1, j);
            }
        }
        // 将 board[][] 中的 '#' 还原为 'O'
        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                if(board[i][j] == '#') {
                    board[i][j] = 'O';
                } else if(board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void mySol(char[][] board, int row, int col, int i, int j) {
        // 递归终止条件
        if(!isValid(row, col, i, j)) {
            return;
        }
        if(board[i][j] == 'X' || board[i][j] == '#') {
            return;
        }
        // board[i][j] 
        board[i][j] = '#'; // [i, j] == O 进行标记，该点表示 O 可以到达
        mySol(board, row, col, i + 1, j);
        mySol(board, row, col, i - 1, j);
        mySol(board, row, col, i, j - 1);
        mySol(board, row, col, i, j + 1);
    }

    private boolean isValid(int row, int col, int i, int j) {
        if(i < 0 || j < 0) {
            return false;
        }
        if(i >= row || j >= col) {
            return false;
        }
        return true;
    }
}

---

输出