leetcode 130. Surrounded Regions（被围绕的区域）

野性酷女 2022-12-03 09:46 124阅读 0赞

[https://leetcode.com/problems/surrounded-regions/][https_leetcode.com_problems_surrounded-regions]

### 一、问题描述 ###

给定一个元素均为'O'和'X'的二维数组，将内部的'O'重置为'X'，边界上的'O'保持不变。

测试用例：

Input：
    X X X X
    X O O X
    X X O X
    X O X X
    
    Output：
    X X X X
    X X X X
    X X X X
    X O X X

### 二、代码实现 ###

首先，遍历四条边界，如果当前元素是'X'，直接continue；如果当前元素是'O'，则将其置为'A'（标记），并且将与它相邻的所有'O'也置为'A'。

然后，两层循环遍历数组，将'O'置为'X'，将'A'恢复为'O'。

class Solution {
        public void solve(char[][] board) {
            if (board == null || board.length <= 2) {
                return;
            }
    
            //记住左右边界的'O'
            for (int i=0; i<board.length; i++) {
                dfs(board, i, 0);
                dfs(board, i, board[0].length-1);
            }
            //记住上下边界的'O'
            for (int j=1; j<board[0].length; j++) {
                dfs(board, 0, j);
                dfs(board, board.length-1, j);
            }
    
            //将内部的'O'置为'X'，同时将边界的'O'还原
            for (int i=0; i<board.length; i++) {
                for (int j=0; j<board[0].length; j++) {
                    if (board[i][j] == 'A') {
                        board[i][j] = 'O';
                    } else if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                }
            }
        }
    
        private void dfs(char[][] board, int i, int j) {
            if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == 'X') {
                return;
            }
    
            board[i][j] = 'A';
            if (i-1 >= 0 && board[i-1][j] == 'O') {   //上 这里的边界判断其实可以去掉
                dfs(board, i-1, j);
            }
            if (i+1 < board.length && board[i+1][j] == 'O') { //下
                dfs(board, i+1, j);
            }
            if (j-1 >= 0 && board[i][j-1] == 'O') { //左
                dfs(board, i, j-1);
            }
            if (j+1 < board[0].length && board[i][j+1] == 'O') { //右
                dfs(board, i, j+1);
            }
        }
    }

[https_leetcode.com_problems_surrounded-regions]: https://leetcode.com/problems/surrounded-regions/