C++ solution inspired from the game of I-go(20ms)


  • 12
    T

    I guess this question is inspired from Chinese traditional sport—I-go. Here the task is to flip all the dead pieces.

    My solution is common: perform BFS from live pieces('O') on the edges and mark the live pieces with temporary state '+'. After BFS done, scan the whole board to flip remaining 'O' (dead) cells and recover live pieces('+') to 'O'.

    class Solution {
    public:
        int row;
        int col;
        vector<pair<int, int> > move_step; 
    
        void bfs(vector<vector<char> > &board, int r, int c) {
            queue<pair<int, int> > qe;
            qe.push({r, c});
    
            while(!qe.empty()) {        
                r = qe.front().first;
                c = qe.front().second;
                qe.pop();
                for(int i = 0; i < 4; i++) {
                    int rr = r + move_step[i].first;
                    int cc = c + move_step[i].second; 
                    if(rr >= 0 && rr < row
                            && cc >= 0 && cc < col
                             && board[rr][cc] == 'O') {
                        board[rr][cc] = '+';
                        qe.push({rr, cc});
                    }
                }
            }
    
            return;
        }
    
        void solve(vector<vector<char> > &board) {
            if (board.empty())
                return;
                                             
            row = board.size();        
            col = board[0].size();        
    
            move_step.resize(4);
            move_step[0] = {0,-1};
            move_step[1] = {0,1};
            move_step[2] = {-1,0};
            move_step[3] = {1,0};
    
            // BFS from four edges and mark  non-surrounded(dead) cells with '+' sign
            
            // top edge
            for(int i = 0; i < col; i++) {
                if(board[0][i] == 'O') {
                    board[0][i] = '+';
                    bfs(board, 0, i);
                }
            }
    
            // bottom edge
            for(int i = 0; i < col; i++) {
                if(board[row-1][i] == 'O') {
                    board[row-1][i] = '+';
                    bfs(board, row-1, i);
                }
            }
            
            // left edge
            for(int i = 1; i < row-1; i++) {
                if(board[i][0] == 'O') {
                    board[i][0] = '+';
                    bfs(board, i, 0);
                }
            }
    
            // right edge
            for(int i = 1; i < row-1; i++) {
                if(board[i][col-1] == 'O') {
                    board[i][col-1] = '+';
                    bfs(board, i, col-1);
                }
            }
            
            // then scan all the cells, recover live cells and flip dead cells 
            for(int i = 0; i < row; i++) 
                for(int j = 0; j < col; j++) {
                    char cur = board[i][j];
                    // recover live cell marked with '+' to 'O'
                    if(cur == '+') 
                        board[i][j] = 'O';
                    // flip dead cell to '*'
                    else if(cur == 'O') 
                        board[i][j] = 'X';
                }
    
            return;
        }
    };

  • 0
    S

    It took me 32ms to run your code :)


  • 0
    L

    I use a queue<int> instead of your queue<pair> and got a time limit exceeded.

    I push 2 integers as a pair and pop 2 integers every iteration.

    I'm a little confused.

    class Solution {
    public:
        void solve(vector<vector<char> > &board) {
            if (board.size() < 3) return;
            if (board[0].size() < 3) return;
            for (int i = 0; i < board[0].size(); i++) // search upside and downside
            {
                if (board[0][i] == 'O')
                    bfs(board, 0, i);
                if (board[board.size()-1][i] == 'O')
                    bfs(board, board.size()-1, i);
            }
            for (int i = 1; i < board.size()-1; i++) // search right and left
            {
                if (board[i][0] == 'O')
                    bfs(board, i, 0);
                if (board[i][board[0].size()-1] == 'O')
                    bfs(board, i, board[0].size()-1);
            }
            for (int i = 0; i < board.size(); i++)
                for (int j = 0; j < board[i].size(); j++)
                    if (board[i][j] == '+') 
                        board[i][j] = 'O';
                    else
                        board[i][j] = 'X';
        }
        
        void bfs(vector<vector<char> > &board, int row, int col)
        {
            queue<int> locs;
            locs.push(row); // push row first then col
            locs.push(col);
            while (locs.empty() == false)
            {
                int i = locs.front(); // get row first then col
                locs.pop();
                int j = locs.front();
                locs.pop();
                board[i][j] = '+';
                if (i > 0 && board[i-1][j] == 'O') {locs.push(i-1);locs.push(j);}
                if (i+1 < board.size() && board[i+1][j] == 'O') {locs.push(i+1);locs.push(j);}
                if (j > 0 && board[i][j-1] == 'O') {locs.push(i);locs.push(j-1);}
                if (j+1 < board[0].size() && board[i][j+1] == 'O') {locs.push(i);locs.push(j+1);}
            }
        }
    };

Log in to reply
 

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