C++ Non-recusive solution, using deque


  • 0
    A

    Not particularly good, not particularly bad either. Just ordinary.

    60 / 60 test cases passed
    Status: Accepted
    Runtime: 13 ms

    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            int h = board.size()-1, w = h >= 0 ? board[0].size()-1 : 0;
            if (h < 2 || w < 2) return;
            deque<array<uint, 2>> q;
            for (uint i = 0; i <= h; i += h) {
                for (uint j = 0; j <= w; j++)
                    if (board[i][j] == 'O') {
                        board[i][j] = 'S';
                        if (i > 0 && board[i-1][j] == 'O') { board[i-1][j] = 'S'; q.push_back({i-1, j}); }
                        if (i < h && board[i+1][j] == 'O') { board[i+1][j] = 'S'; q.push_back({i+1, j}); }
                    }
            }
            for (uint i = 1; i < h; i++) {
                for (uint j = 0; j <= w; j += w)
                    if (board[i][j] == 'O') {
                        board[i][j] = 'S';
                        if (j > 0 && board[i][j-1] == 'O') { board[i][j-1] = 'S'; q.push_back({i, j-1}); }
                        if (j < w && board[i][j+1] == 'O') { board[i][j+1] = 'S'; q.push_back({i, j+1}); }
                    }
            }
            while (!q.empty()) {
                uint i = q.front()[0], j = q.front()[1];
                q.pop_front();
                if (i > 0 && board[i-1][j] == 'O') { board[i-1][j] = 'S'; q.push_back({i-1, j}); }
                if (i < h && board[i+1][j] == 'O') { board[i+1][j] = 'S'; q.push_back({i+1, j}); }
                if (j > 0 && board[i][j-1] == 'O') { board[i][j-1] = 'S'; q.push_back({i, j-1}); }
                if (j < w && board[i][j+1] == 'O') { board[i][j+1] = 'S'; q.push_back({i, j+1}); }
            }
            for (uint i = 0; i <= h; i++) {
                for (uint j = 0; j <= w; j++) {
                    if (board[i][j] == 'O') board[i][j] = 'X';
                    else if (board[i][j] == 'S') board[i][j] = 'O';
                }
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.