Why do I have the "Memory Limit Exceeded" with BFS?


  • 0
    X

    I am am using BFS to check all characters on the four sides: turning all possible 'O' to 'T'. At the final stage I reset 'O' to 'X' and 'T' to 'O'. I don't see why I would have this memory exceed problem. Anybody could kindly point out what I missed?

    class Solution {
    public:
        void solve(vector<vector<char>> &board) {
            int nrow=board.size();
            if(nrow<3){return;}
            int ncol=board[0].size();
            if(ncol<3){return;}
            CheckRow(board,0,0,ncol-1);
            CheckRow(board,nrow-1,0,ncol-1);
            CheckCol(board,0,1,nrow-2);
            CheckCol(board,ncol-1,1,nrow-2);
            for(int i=0;i<nrow;i++){
                for(int j=0;j<ncol;j++){
                    if(board[i][j]=='O'){board[i][j]='X';}
                    else if(board[i][j]=='T'){board[i][j]='O';}
                }
            }
        }
        
        void CheckRow(vector<vector<char> > &board,int i, int left, int right){
            int nrow=board.size();int ncol=board[0].size();
            for(int j=left;j<=right;j++){
                if(board[i][j]=='O'){
                    queue<pair<int,int> > q;
                    q.push(make_pair(i,j));
                    while(not(q.empty())){
                        pair<int,int> current=q.front();q.pop();
                        int ii=current.first,jj=current.second;
                        board[i][j]='T';
                        if(ii>0 and board[ii-1][jj]=='O'){q.push(make_pair(ii-1,jj));}
                        if(ii<nrow-1 and board[ii+1][jj]=='O'){q.push(make_pair(ii+1,jj));}
                        if(jj>0 and board[ii][jj-1]=='O'){q.push(make_pair(ii,jj-1));}
                        if(jj<ncol-1 and board[ii][jj+1]=='O'){q.push(make_pair(ii,jj+1));}
                    }
                }
            }
        }
        
        void CheckCol(vector<vector<char> > &board,int j, int top, int bottom){
            int nrow=board.size();int ncol=board[0].size();
            for(int i=top;i<=bottom;i++){
                if(board[i][j]=='O'){
                    queue<pair<int,int> > q;
                    q.push(make_pair(i,j));
                    while(not(q.empty())){
                        pair<int,int> current=q.front();q.pop();
                        int ii=current.first,jj=current.second;
                        board[i][j]='T';
                        if(ii>0 and board[ii-1][jj]=='O'){q.push(make_pair(ii-1,jj));}
                        if(ii<nrow-1 and board[ii+1][jj]=='O'){q.push(make_pair(ii+1,jj));}
                        if(jj>0 and board[ii][jj-1]=='O'){q.push(make_pair(ii,jj-1));}
                        if(jj<ncol-1 and board[ii][jj+1]=='O'){q.push(make_pair(ii,jj+1));}
                    }
                }
            }
        }
    };

Log in to reply
 

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