C++ BFS 50%


  • 0
    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& grid) {
            int m = grid.size();
            int n = grid[0].size();
            int ans;
            vector<pair<int,int>> direct = {{0,-1},{-1,0},{0,1},{1,0}};
            vector<vector<int>> cnt(m,vector<int>(n,0));
            
            int level = 0;
            
            for(int i=0;i<m;i++) {
                for(int j=0;j<n;j++) {
                    if(grid[i][j]!=1) continue;
                    ans = INT_MAX;
                    vector<vector<int>> onePass(m,vector<int>(n,0));
                    queue<pair<int,int>> q;
                    q.push({i,j});
                    while(!q.empty()) {
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();
                        for(auto dir : direct) {
                            int nx = x+dir.first;
                            int ny = y+dir.second;
                            if(nx<0 || ny<0 || nx>m-1 || ny>n-1 || grid[nx][ny]!=level) continue; // only search slot that has been visited previously, otherwise ans = -inf
                            onePass[nx][ny] = onePass[x][y]+1;
                            cnt[nx][ny] += onePass[nx][ny];
                            ans = min(ans,cnt[nx][ny]);
                            grid[nx][ny]--; // flag visited slot for next round
                            q.push({nx,ny});
                        }
                    }
                    level --;
                }
            }
    
            return ans==INT_MAX?-1:ans;
        }
    };
    

Log in to reply
 

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