题解 | #牛群的活动区域#

考察的知识点：深度优先搜索；

解答方法分析：

1. 检查输入矩阵是否为空或者数、列数是否为零，如果是，则直接返回原矩阵。
2. 获取矩阵的行数 m 和列数 n。
3. 遍历第一行最后一行，对于边界上的 ‘O’，利用深度优先搜索（DFS）将其与边界上的 ‘O’ 相连接的区域置为 ‘B’，表示不被包围的区域。
4. 遍历一列和最后一列，对于边界上的 ‘O’，同样进行深度优先搜索，将其与边界上的 ‘O’ 相连的区域置为 ‘B’。
5. 遍历整个矩阵，将剩余的 ‘B’ 替换为 ‘A’，将 ‘O’ 替换为 ‘X’。
6. 将 ‘B’ 替换为 ‘O’，恢复被包围的 ‘O’ 区域。
7. 返回更新后的矩阵。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    vector<vector<char>> solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) {
            return board;
        }

        int m = board.size();
        int n = board[0].size();

        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }

        for (int j = 1; j < n - 1; j++) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'B') {
                    board[i][j] = 'A';
                } else if (board[i][j] == 'C') {
                    board[i][j] = 'B';
                }
            }
        }

        return board;
    }

  private:
    void dfs(vector<vector<char>>& board, int i, int j) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() ||
                board[i][j] != 'B') {
            return;
        }

        board[i][j] = 'C';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }
};