Why my c++ solution Memory Limit Exceeded? I only used a queue


  • 0
    L

    Here is my code in C++

     void DeleteIsland(vector<vector<char>> &grid, int r_pos,int c_pos){
        int rows = grid.size();
        int cols = grid[0].size();
        list<pair<int,int> > queue;
    	queue.emplace_back(r_pos,c_pos );
    	while(!queue.empty()){
    		auto it = queue.begin();
    		int cur_r = (*it).first ;
    		int cur_c = (*it).second;
    		// up
    		if(cur_r - 1 >=0 && grid[cur_r-1][cur_c] == '1')
    			queue.emplace_back(cur_r-1,cur_c);
    		//down
    		if(cur_r+1<rows && grid[cur_r+1][cur_c] == '1')
    			queue.emplace_back(cur_r+1,cur_c);
    		//left
    		if(cur_c-1>=0 && grid[cur_r][cur_c-1] == '1')
    			queue.emplace_back(cur_r,cur_c-1);
    		//right
    		if(cur_c+1<cols && grid[cur_r][cur_c+1] == '1')
    			queue.emplace_back(cur_r,cur_c+1);
    
    		grid[cur_r][cur_c] = '0';
    		queue.pop_front();
    	}
    }
    
    int numIslands(vector<vector<char>> &grid) {
        if(grid.empty()) return 0;
        int rows = grid.size();
        int cols = grid[0].size();
        int count=0;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(grid[i][j] == '1'){
                    count++;
                    DeleteIsland(grid,i,j);
                }
            }
            
        }
        
        return count;
    }

  • 0

    When you put a place (i, j) into the queue, you should change grid[i][j] to '0'.

    void BFS(vector<vector<char>> &grid, int x, int y)
    {
        queue<vector<int>> q;
        q.push({x, y});
        grid[x][y] = '0';
        
        while(!q.empty())
        {
            x = q.front()[0], y = q.front()[1];
            q.pop();
            
            if(x > 0 && grid[x - 1][y] == '1')
            {
                q.push({x - 1, y});
                grid[x - 1][y] = '0';
            }
            if(x < grid.size() - 1 && grid[x + 1][y] == '1')
            {
                q.push({x + 1, y});
                grid[x + 1][y] = '0';
            }
            if(y > 0 && grid[x][y - 1] == '1')
            {
                q.push({x, y - 1});
                grid[x][y - 1] = '0';
            }
            if(y < grid[0].size() - 1 && grid[x][y + 1] == '1')
            {
                q.push({x, y + 1});
                grid[x][y + 1] = '0';
            }
        }
    }

Log in to reply
 

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