LC 130. Surrounded Regions

https://leetcode.com/problems/surrounded-regions/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    void solve(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n , false));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j] || board[i][j] == 'X') continue;
                bool valid = false;
                vector<pair<int, int>> record;
                record.push_back({i, j});
                int idx = 0;
                while (idx < record.size()) {
                    auto [x, y] = record[idx];
                    if (vis[x][y]) {
                        idx += 1;
                        continue;
                    }
                    vis[x][y] = true;
                    if (x == 0 || y == 0 || x == m - 1 || y == n - 1) valid = true;
                    for (int k = 0; k < 4; k++) {
                        int nx = x + dr[k];
                        int ny = y + dc[k];
                        if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
                        if (board[nx][ny] == 'X' || vis[nx][ny]) continue;
                        record.push_back({nx, ny});
                    }
                    idx += 1;
                }
                if (!valid) {
                    for (auto &[x, y]: record) board[x][y] = 'X';
                }
            }
        }
    }
};

Time Complexity: O(n)
Space: O(n)

算是多次 BFS 找出答案