Sharing my 32ms C++ solution


  • 0
    T
    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            int m = board.size();
            if(m==0)
                return;
            int n = board[0].size();
            if(n==0)
                return;
            
            int i, j;
            queue<pair<int, int>> myQueue;
            vector<pair<int, int>> myVector;
            for(i=0; i<m; i++)
                for(j=0; j<n; j++)
                    if(board[i][j]=='O')
                    {
                        myQueue.push(make_pair(i, j));
                        bool survived = false;
                        board[i][j] = 'V';
                        while(myQueue.size()>0)
                        {
                            pair<int, int> tmp = myQueue.front();
                            myQueue.pop();
                            myVector.push_back(make_pair(tmp.first, tmp.second));
                            
                            if(tmp.first==0 || tmp.first==m-1 | tmp.second==0 || tmp.second==n-1)
                                survived = true;
                                
                            if(tmp.first-1>=0&&board[tmp.first-1][tmp.second]=='O')
                            {
                                myQueue.push(make_pair(tmp.first-1, tmp.second));
                                board[tmp.first-1][tmp.second] = 'V';
                            }
                            if(tmp.first+1<m&&board[tmp.first+1][tmp.second]=='O')
                            {
                                myQueue.push(make_pair(tmp.first+1, tmp.second));
                                board[tmp.first+1][tmp.second] = 'V';
                            }
                            if(tmp.second-1>=0&&board[tmp.first][tmp.second-1]=='O')
                            {
                                myQueue.push(make_pair(tmp.first, tmp.second-1));
                                board[tmp.first][tmp.second-1] = 'V';
                            }
                            if(tmp.second+1<n&&board[tmp.first][tmp.second+1]=='O')
                            {
                                myQueue.push(make_pair(tmp.first, tmp.second+1));
                                board[tmp.first][tmp.second+1] = 'V';
                            }
                        }
                        
                        if(survived==false)
                        {
                            for(int k=0; k<myVector.size(); k++)
                                board[myVector[k].first][myVector[k].second] = 'X';
                        }
                        
                        myVector.clear();
                    }
                    
            for(i=0; i<m; i++)
                for(j=0; j<n; j++)
                    if(board[i][j]=='V')
                        board[i][j] = 'O';
        }
    };

Log in to reply
 

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