Leetcode Surrounded Regions https://oj.leetcode.com/problems/surrounded-regions/

leetcode-surrounded-regions.cc

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

class Solution {
    public:
        void solve(vector< vector<char> > &board);
};

void Solution::solve(vector< vector<char> > &board) {
    int n = board.size();
    if (n == 0) return;
    int m = board[0].size();
    
    queue< pair<int, int> > Q;
    for (int i = 0; i < n; ++ i) {
        if (board[i][0] == 'O') {
            Q.push(make_pair(i, 0));
            board[i][0] = '-';
        }
        if (board[i][m - 1] == 'O') {
            Q.push(make_pair(i, m - 1));
            board[i][m - 1] = '-';
        }
    }
    for (int i = 0; i < m; ++ i) {
        if (board[0][i] == 'O') {
            Q.push(make_pair(0, i));
            board[0][i] = '-';
        }
        if (board[n - 1][i] == 'O') {
            Q.push(make_pair(n - 1, i));
            board[n - 1][i] = '-';
        }
    }

    while (!Q.empty()) {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        for (int i = 0; i < 4; ++ i) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && board[xx][yy] == 'O') {
                board[xx][yy] = '-';
                Q.push(make_pair(xx, yy));
            }
        }
    }

    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            board[i][j] = (board[i][j] == '-' ? 'O' : 'X');
}