6ms c++ BFS solution beats 97.09%


  • 0
    K

    tiny improvement from StefanPochmann's BFS search version (great idea on traversing reachable-by-all-past-building only cells, which dramatically reduces search space)

    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& grid) {
            if(!grid.size()||!grid[0].size())return -1;
            int m=grid.size(),n=grid[0].size();
            
            int dx[]={-1,1,0,0},dy[]={0,0,-1,1},dis,bnum=0;
            int vsum[m][n];
            for(int i=0;i<m;i++)fill_n(vsum[i],n,0);
            int result=INT_MAX;
            
            for(int i=0;i<m;i++)for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    result=INT_MAX,dis=1;
                    queue<pair<int,int>>q;
                    q.push({i,j});
                    while(!q.empty()){
                        int cnt=q.size();
                        for(int i=0;i<cnt;i++){
                            pair<int,int>n1=q.front();q.pop();
                            for(int j=0;j<4;j++){
                                int a=n1.first+dx[j],b=n1.second+dy[j];
                                if(a<0||a>=m||b<0||b>=n||grid[a][b]!=-bnum)continue;
                                vsum[a][b]+=dis,grid[a][b]--;
                                result=min(result,vsum[a][b]);
                                q.push({a,b});
                            }
                        }
                        dis++;
                    }
                    bnum++;
                }
            }
            return result==INT_MAX?-1:result;
        }
    };
    

Log in to reply
 

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