130. Surrounded Regions

Published on April 8, 2023

Question

This question says that there is a checkerboard board with 'X' and 'O' on it. Flip all 'O's into 'X's. The rule is that 'O' at the boundary cannot be flipped and 'O' connected to 'O' which cannot be reversed cannot be flipped.

Algorithm

This topic is more intuitive approach is to first dfs the border of the grid once, to find the grid connected to it, are marked as visited. after the non-border grid traversal and the execution of dfs, then the border and its connected grid are visited, the remaining can dfs to and is 'O' can be flipped. My code 1 is this idea. Time and space complexity are O(m * n).

Code 2 is a previous commit, should be a reference to the standard answer. There are two ingenious ideas. The first one is to reduce some duplicate code in finding node neighbors by defining DIRECTIONS array; another better ingenuity is that he does not define an additional visited array to store the traversed information, but directly in-place the modified board.

When traversing the boundaries, the boundaries and the squares connected to them are directly set to 'A'. The remaining 'O's on the board can be flipped. At this point, you can directly traverse the board, flip the remaining 'O' to 'X', and then set 'A' to 'O' during the traversal.

Code1

class Solution {
    boolean[][] visited;
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return;
        }
        int m = board.length, n = board[0].length;
        visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O' && !visited[i][0]) {
                dfs(board, i, 0, false);
            }
        }
        for (int i = 0; i < m; i++) {
            if (board[i][n-1] == 'O' && !visited[i][n-1]) {
                dfs(board, i, n-1, false);
            }
        }
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O' && !visited[0][i]) {
                dfs(board, 0, i, false);
            }
        }
        for (int i = 0; i < n; i++) {
            if (board[m-1][i] == 'O' && !visited[m-1][i]) {
                dfs(board, m-1, i, false);
            }
        }
        
        for (int i = 1; i < m-1; i++) {
            for (int j = 1; j < n-1; j++) {
                if (board[i][j] == 'O' && !visited[i][j]) {
                    dfs(board, i, j, true);
                }
            }
        }
    }
    
    private void dfs(char[][] board, int i, int j, boolean flip) {
        Stack<int[]> stack = new Stack();
        stack.push(new int[]{i, j});
        visited[i][j] = true;
        while (!stack.isEmpty()) {
            int[] pair = stack.pop();
            int row = pair[0], col = pair[1];
            if (flip) {
                board[row][col] = 'X';
            }
            if (row - 1 >= 0) {
                int x = row-1, y = col;
                if (board[x][y] == 'O' && !visited[x][y]) {
                    visited[x][y] = true;
                    stack.push(new int[]{x, y});
                }
            }
            if (col - 1 >= 0) {
                int x = row, y = col-1;
                if (board[x][y] == 'O' && !visited[x][y]) {
                    visited[x][y] = true;
                    stack.push(new int[]{x, y});
                }
            }
            if (row + 1 < board.length) {
                int x = row+1, y = col;
                if (board[x][y] == 'O' && !visited[x][y]) {
                    visited[x][y] = true;
                    stack.push(new int[]{x, y});
                }
            }
            if (col + 1 < board[0].length) {
                int x = row, y = col+1;
                if (board[x][y] == 'O' && !visited[x][y]) {
                    visited[x][y] = true;
                    stack.push(new int[]{x, y});
                }
            }
            
        }
    }
}

Code2

class Solution {
    protected static int[][] DIRECTIONS = {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };
    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                dfs(board, i, n - 1);
            }
        }

        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                dfs(board, 0, i);
            }
            if (board[m - 1][i] == 'O') {
                dfs(board, m - 1, i);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } 
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void dfs(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;
        board[i][j] = 'A';
        for (int[] dir : DIRECTIONS) {
            int x = i + dir[0], y = j + dir[1];
            if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] == 'X' || board[x][y] == 'A') continue;
            dfs(board, x, y);
        }
    }   
}

问题

这个题目是说有一个棋盘board，上面是'X'和'O'。将所有'O'翻转成'X'。规则是边界处的‘O'不可以翻转，连接着不能反转的’O'的‘O'也不能翻转。

算法

这个题目比较直观的做法就是先将边界的格子dfs一遍，找到与其连接的格子，都标记为visited。之后在将非边界的格子遍历并执行dfs，这时边界的以及与其相连的格子都是visited，剩余的还能dfs到的且是'O'的都可以翻转。我的代码1就是这个思路。时间和空间复杂度都是O(m*n)。

代码2是之前的提交，应该是参考了标准答案。有两个巧思。第一个是通过定义DIRECTIONS数组，减少一些重复代码在寻找节点邻居的时候；另一个更好的巧思是，他没有额外定义一个visited数组去储存遍历过的信息，而是直接inplace的修改了棋盘。

在遍历边界的时候，直接将边界以及连接边界的格子置为'A'。后续那么棋盘上剩下的'O'肯定是可以翻转的。此时直接遍历棋盘即可，将剩下的'O'翻转为'X'，之后再将遍历过程中的'A'置为'O'即可。

代码1

略

代码2

略