Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 130. Surrounded Regions

---

參考資訊：
https://www.cnblogs.com/grandyang/p/4555831.html

題目：


方法：

跟邊邊連通的，都是要保留的，其餘轉成'X'即可

解答：

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        int n = board[0].size();

        auto dfs = [&](this auto&& dfs, int i, int j) -> void {
            if (i < 0 || i >= m || j < 0 || j >= n) {
                return;
            }
            if (board[i][j] != 'O') {
                return;
            }

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

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && 
                    board[i][j] == 'O')
                {
                    dfs(i, j);
                }
            }
        }
        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] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
};