LeetCode130. Surrounded Regions

1、题目链接

https://leetcode.com/problems/surrounded-regions/

2、解题思路

题目意思是给你一个二维数组，这个二维数组的值由字符X和O构成，让你找到所有被X包围的O，并将其填充成X，边界上的O是不会被填充的，换句话说，和边界的O相连的O也不会被填充，这样的话我们就只需要找到与边界的O相连的O，怎么找呢？我的想法是遍历整个边界，当遍历到是O时，递归搜索其上下左右四个位置，如果是O，那么将其标记为已访问，最后重新遍历数组，当你遍历到数组中某个O未被访问时，那么它肯定是被X包围的，将其变成X就行了；还有一种做法是，在你递归搜索的时候将你遍历到的O变成另外一个字符，这样就代表你访问过了这个点，原理和上述是一样的。

3、代码

解法1：

class Solution {
    public void solve(char[][] board) {
        if (null == board || board.length == 0) {
            return;
        }
        int rowLength = board.length;
        int colLength = board[0].length;
        boolean[][] isVisited = new boolean[rowLength][colLength];
        for (int i = 0; i < rowLength; i++) {
            if (board[i][0] == 'O') {
                dfs(board, isVisited, i, 0, rowLength, colLength);
            }
            if (board[i][colLength - 1] == 'O') {
                dfs(board, isVisited, i, colLength - 1, rowLength, colLength);
            }
        }
        for (int j = 0; j < colLength; j++) {
            if (board[0][j] == 'O') {
                dfs(board, isVisited, 0, j, rowLength, colLength);
            }
            if (board[rowLength - 1][j] == 'O') {
                dfs(board, isVisited, rowLength - 1, j, rowLength, colLength);
            }
        }

        for (int i = 0; i < rowLength; i++) {
            for (int j = 0; j < colLength; j++) {
                if (board[i][j] == 'O' && !isVisited[i][j]) {
                    board[i][j] = 'X';
                }
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
    
     public void dfs(char[][] board, boolean[][] isVisited, int i, int j, int row, int col) {
        if (i < 0 || j < 0 || i >= row || j >= col || isVisited[i][j] || board[i][j] != 'O') {
            return;
        }
        isVisited[i][j] = true;
        dfs(board, isVisited, i - 1, j, row, col);
        dfs(board, isVisited, i + 1, j, row, col);
        dfs(board, isVisited, i, j - 1, row, col);
        dfs(board, isVisited, i, j + 1, row, col);
    }
}

解法2：

public void solve(char[][] board) {
    if (null == board || board.length == 0) {
        return;
    }
    int rowLength = board.length;
    int colLength = board[0].length;
    for (int i = 0; i < rowLength; i++) {
        if (board[i][0] == 'O') {
            dfs(board, i, 0, rowLength, colLength);
        }
        if (board[i][colLength - 1] == 'O') {
            dfs(board, i, colLength - 1, rowLength, colLength);
        }
    }
    for (int j = 0; j < colLength; j++) {
        if (board[0][j] == 'O') {
            dfs(board, 0, j, rowLength, colLength);
        }
        if (board[rowLength-1][j] == 'O') {
            dfs(board, rowLength - 1, j, rowLength, colLength);
        }
    }
    for (int i = 0; i < rowLength; i++) {
        for (int j = 0; j < colLength; j++) {
            if (board[i][j] == 'O') {
                board[i][j] = 'X';
            }
            if (board[i][j] == 'Q') {
                board[i][j] = 'O';
            }
        }
    }
}

public void dfs(char[][] board, int i, int j, int row, int col) {
        if (i < 0 || j < 0 || i >= row || j >= col || board[i][j] != 'O') {
            return;
        }
        board[i][j] = 'Q';
        dfs(board, i - 1, j, row, col);
        dfs(board, i + 1, j, row, col);
        dfs(board, i, j - 1, row, col);
        dfs(board, i, j + 1, row, col);
 }

4、结果

QQ20190701-221434@2x.png