Why do BFS from '0'(empty land) to '1'(building) get TLE?


  • 0
    W

    Codes in discuss do BFS from '1' to '0' are accepted, while my code do BFS from '0' to '1' can't pass the big test. Can anyone tell me the reason? Thanks.
    Here's my code:

    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& grid) {
        int m=grid.size();
        if(!m) return -1;
        int n=grid[0].size();
        if(!n) return -1;
        int count=0;
        int mindist=INT_MAX;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(grid[i][j]==1)
                    count++;
        if(!count) return -1;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                vector<vector<bool>> isvisited(m,vector<bool>(n,false));
                mindist=min(mindist,BFS(i,j,count,grid,isvisited));
                }
            }
        return mindist;
        }
    private:
        int BFS(int x,int y,int count,vector<vector<int>>& grid,vector<vector<bool>>& isvisited){
        int m=grid.size();
        int n=grid[0].size();
        int dist=0;
        int layer=0;
        queue<pair<int,int>> q;
        q.push({x,y});
        vector<pair<int,int>> directions{{-1,0},{1,0},{0,-1},{0,1}};
        while(!q.empty()){
            int cursize=q.size();
            layer++;
            for(int i=0;i<cursize;i++){
                pair<int,int> cur=q.front();
                q.pop();
                isvisited[cur.first][cur.second]=true;
                for(auto d:directions){
                    int nextx=cur.first+d.first;
                    int nexty=cur.second+d.second;
                    if(nextx>=0&&nextx<m&&nexty>=0&&nexty<n&&!isvisited[nextx][nexty]){
                        if(grid[nextx][nexty]==0)
                            q.push({nextx,nexty});
                        if(grid[nextx][nexty]==1){
                            count--;
                            dist+=layer;
                            isvisited[nextx][nexty]=true;
                        }
                        if(count==0) return dist;
                    }
                }
            }
        }
        return -1;
        }
    };
    

    While my code do BFS from '1' to '0' can be accepted:

    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& grid) {
        int m=grid.size();
        if(!m) return -1;
        int n=grid[0].size();
        if(!n) return -1;
        int count=0;
        int mindist=INT_MAX;
        vector<vector<int>> dist(m,vector<int>(n,0));
        vector<vector<int>> counts(m,vector<int>(n,0));
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                count++;
                vector<vector<bool>> isvisited(m,vector<bool>(n,false));
                BFS(i,j,grid,isvisited,dist,counts);
                }
            }
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(grid[i][j]==0&&counts[i][j]==count)
                    mindist=min(mindist,dist[i][j]);
        return mindist==INT_MAX?-1:mindist;
        }
    private:
        void BFS(int x,int y,vector<vector<int>>& grid,vector<vector<bool>>& isvisited,vector<vector<int>>& dist,vector<vector<int>> &counts){
        int m=grid.size();
        int n=grid[0].size();
        int layer=0;
        queue<pair<int,int>> q;
        q.push({x,y});
        vector<pair<int,int>> directions{{-1,0},{1,0},{0,-1},{0,1}};
        while(!q.empty()){
            int cursize=q.size();
            layer++;
            for(int i=0;i<cursize;i++){
                pair<int,int> cur=q.front();
                q.pop();
                isvisited[cur.first][cur.second]=true;
                for(auto d:directions){
                    int nextx=cur.first+d.first;
                    int nexty=cur.second+d.second;
                    if(nextx>=0&&nextx<m&&nexty>=0&&nexty<n&&!isvisited[nextx][nexty]&&grid[nextx][nexty]==0){
                        dist[nextx][nexty]+=layer;
                        counts[nextx][nexty]++;
                        q.push({nextx,nexty});
                        isvisited[nextx][nexty]=true;
                    }
                }
            }
        }
        }
    };

  • 1
    L

    Based on my guess, the 1 nodes is much less than the 0 nodes, which means you do much more breath and calculation if you start from 0s. This is also the reason why I choose BFS from 1 nodes to 0 nodes.
    Hope this can help you.


  • 0
    W

    Hi, thank you lchen. Yes, I have the same guess, your code start from '0' also get TLE??


Log in to reply
 

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