130. 被围绕的区域

深度优先搜索

class Solution {

    int m;
    int n;
    boolean[][] used;
    int[][] move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public void solve(char[][] board) {

        m = board.length;
        n = board[0].length;
        used = new boolean[m][n];

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                /**
                 * 逆向思维
                 * 题目要找出被包围且不是边界的O，但是这很麻烦
                 * 因此可以从边界上的O开始，遍历所有和它相连的O，将其标记为true
                 * 最后所有标记为false的O都要被替换
                 */
                if (board[i][j] == 'O' && !used[i][j] && (i == 0 || i == m - 1 || j == 0 || j == n - 1)) {
                    dfs(board, i, j);
                }
            }
        }

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (board[i][j] == 'O' && !used[i][j]) {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void dfs(char[][] board, int row, int col) {

        used[row][col] = true;

        for (int i = 0; i < 4; i++) {

            int newRow = row + move[i][0];
            int newCol = col + move[i][1];

            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !used[newRow][newCol] && board[newRow][newCol] == 'O') {
                dfs(board, newRow, newCol);
            }
        }
    }
}

/**
 * 时间复杂度 O(m×n)
 * 空间复杂度 O(m×n)
 */

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