題目網址：https://leetcode.cn/problems/surrounded-regions/

題意：給一 m x n 的矩陣 board, 由若干個 char 'X' 和 'O', 找到所有被 'X' 圍繞的區域, 並用 'X' 來替代這些區域裡的 'O'。

Solution：

想法：利用 DFS, 題目希望我們找出被 X 包圍的區域, 但我們可以反向思考, 從邊界出發（因為邊界上的 O 一定不會被 X 包圍）, 往內陸延伸找出那些沒有被 X 包圍的區域, 概念同 417. Pacific Atlantic Water Flow。因此步驟如下：

  • 找出沒有被 X 包圍的 O 區域, 並把這些區域設為 #（區分是否被 X 包圍）
  • 遍歷 board, 將 O 設為 X（因為沒被設為 # 的區域就是被 X 包圍的 O 區域）
  • 遍歷 board, 將 # 設為 O
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        m = board.size(), n = board[0].size();

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

        for (int j = 0; j < n; ++j) {
            dfs(board, 0, j); // top
            dfs(board, m - 1, j); // bottom
        }

        replace(board);
    }

private:
    int m, n;
    vector<pair<int, int>> dirs = {
        {0, 1}, {0, -1},
        {1, 0}, {-1, 0}
    };

    void dfs(vector<vector<char>>& board, const int i, const int j){
        if (outOfBound(i, j) || board[i][j] != 'O') {
            return;
        }

        board[i][j] = '#'; // 將沒有被 X 包圍的 O 設成 #

        for (const auto& [dirY, dirX] : dirs) {
            dfs(board, i + dirY, j + dirX);
        }
    }

    bool outOfBound(const int i, const int j){
        if (i < 0 || i == m || j < 0 || j == n) {
            return true;
        }
        return false;
    }

    void replace(vector<vector<char>>& board){
        // 先將被包圍的 O 設成 X
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }

        // 再將沒被包圍的 # 設成 O
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
};
  • time：$O(m \cdot n)$ ➔ 遍歷 board
  • space：$O(m \cdot n)$ ➔ 取決於遞迴深度, worse case：整個 board 皆為 'O'