leetcode130：被围绕的区域

题目

思路一：dfs

从边界开始搜，将与边界元素‘O’联通的‘O’置为‘#’，递归遍历完之后整个矩阵中只存在'X', 'O', '#'三种元素，此时矩阵中的'O'全部被'X'包围，然后将'O'全部改为'X', 将'#' 全部改为'O'。

class Solution {
    int rows, cols;
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return ;
        rows = board.length; 
        cols = board[0].length;
        for (int i = 0; i < rows; i++) {
            if (board[i][0] == 'O') {
                change(i, 0, board);
            }
            if (board[i][cols-1] == 'O') {
                change(i, cols - 1, board);
            }
        }
        for (int i = 1; i < cols - 1; i++) {
            if (board[0][i] == 'O') {
                change(0, i, board);
            }
            if (board[rows - 1][i] == 'O') {
                change(rows - 1, i, board);
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void change(int i, int j, char[][] board) {
        if (i < 0 || i >= rows || j < 0 || j >= cols) return;
        if (board[i][j] == 'O') {
            board[i][j] = '#';
            change(i, j - 1, board);
            change(i, j + 1, board);
            change(i - 1, j, board);
            change(i + 1, j, board);
        }
    }
}

思路二：并查集

leetcode题解