Leetcode - 130. 被围绕的区域

class Solution {

    //   X O X X   |   假设输入的二维矩阵如左图所示，不妨把该矩阵当作内存，字符'O'代表内存中的对象
    //   X O X X   |   那么题目就相当于要我们进行一次垃圾回收，把所有的垃圾对象改成'X'
    //   X X O X   |   内存中最外层的'O'相当于GC Roots，只要内存中的对象能和GC Roots关联上，则该对象不会被回收
    //   X O X X   |   没有和GC Roots关联上的对象就会被回收
    // 主要解题思路：将最外层的'O'都标记为存活的，用'S'表示，然后将'S'周围的'O'也标记为'S'
    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        
        // 找到第一行的'O'，将它标记为'S'
        for (int i = 0; i < n; i++) {
            mark(board, 0, i, m, n);
        }

        // 找到最后一行的'O'，将它标记为'S'
        for (int i = 0; i < n; i++) {
            mark(board, m - 1, i, m, n);
        }

        // 找到第一列的'O'，将它标记为'S'
        for (int i = 0; i < m; i++) {
            mark(board, i, 0, m, n);
        }

        // 找到最后一列的'O'，将它标记为'S'
        for (int i = 0; i < m; i++) {
            mark(board, i, n - 1, m, n);
        }

        // 标记完成后，标记为'S'的对象不能被回收，而仍然为'O'的对象就是垃圾，要被回收
        // 因此遍历整个二维矩阵，发现了'S'就把它改成'O'，发现了'O'就把它改成'X'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] != 'X') {
                    board[i][j] = board[i][j] == 'S' ? 'O' : 'X';
                }
            }
        }
    }

    // 用于将board[x][y]标记为不会被回收，用'S'表示
    // 将board[x][y]标记为不会被回收后，还要将它上下左右四个点也标记为不会被回收
    private static void mark(char[][] board, int x, int y, int m, int n) {

        // 如果board[x][y]不存在，或者不是'O'，则不做任何事
        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') {
            return;
        }

        // 将该点标记为存活的
        board[x][y] = 'S';

        // 将周围的'O'也标记为存活的
        mark(board, x, y - 1, m, n);
        mark(board, x, y + 1, m, n);
        mark(board, x - 1, y, m, n);
        mark(board, x + 1, y, m, n);
    }
}