讨论/《广度优先搜索》 - 练习:被围绕的区域/
《广度优先搜索》 - 练习:被围绕的区域
共 1 个回复

广度优先搜索

1.将四周的'O'区域做上标记

2.将中间没有被标记的'O'改成'X'

class Solution {
public:
    int direct[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    bool valid(int i, int j, int m, int n){
        return i >= 0 && i < m && j >= 0 && j < n;
    }
    void solve(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        vector<vector<int>> vis(m, vector<int>(n, 0));
        queue<pair<int, int>> q;
        //1.先将四周的'O'区域做好标记
        for(int i = 0; i < m; i++){
            if(board[i][0] == 'O') q.push({i, 0});
            if(board[i][n - 1] == 'O') q.push({i, n - 1});
        }
        for(int i = 0; i < n; i++){
            if(board[0][i] == 'O') q.push({0, i});
            if(board[m - 1][i] == 'O') q.push({m - 1, i});
        }
        while(!q.empty()){
            auto [x, y] = q.front(); q.pop();
            for(int i = 0; i < 4; i++){
                int newx = x + direct[i][0];
                int newy = y + direct[i][1];
                if(valid(newx,newy,m,n) && board[newx][newy] == 'O' && !vis[newx][newy]){
                    vis[newx][newy] = 1;
                    q.push({newx,newy});
                }
            }
        }
        //2.将中间的没有被标记的'O'改成'X'
        for(int i = 1; i < m - 1; i++){
            for(int j = 1; j < n - 1; j++){
                if(board[i][j] == 'O' && !vis[i][j]) board[i][j] = 'X';
            }
        }
    }
};