C++ Solution using BFS


  • 0
    Y
    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& grid) {
            int ans;
            if(!grid.size())
                return -1;
            int n = grid.size(), m = grid[0].size();
            int cnt = 3;
            vector<vector<int> > vis(n, vector<int>(m)), reachhousecnt(n, vector<int>(m));
            vector<vector<int> > mp(n, vector<int>(m)), tmp(n, vector<int>(m));
            ans = INT_MAX;
            bool hasempty = false, reachtoAllhouse = false;
            int houseTot = 0;
            for(int i = 0; i < n; ++ i){
                for(int j = 0; j < m; ++ j){
                    if(grid[i][j] == 0)
                        hasempty = true;
                    if(grid[i][j] == 1){
                        queue<pair<int,int>> q;
                        q.push(make_pair(i, j));
                        tmp[i][j] = mp[i][j] = 0;
                        ++ houseTot;
                        while(!q.empty()){
                            pair<int,int> cur = q.front();
                            q.pop();
                            for(int k = 0; k < 4; ++ k){
                                int ntx = cur.first + dir[k][0], nty = cur.second + dir[k][1];
                                if(ntx >= 0 && ntx < n && nty >= 0 && nty < m && grid[ntx][nty] == 0 && vis[ntx][nty] != cnt){
                                    mp[ntx][nty] += (tmp[cur.first][cur.second] + 1);
                                    tmp[ntx][nty] = tmp[cur.first][cur.second] + 1;
                                    vis[ntx][nty] = cnt;
                                    ++ reachhousecnt[ntx][nty];
                                    q.push(make_pair(ntx, nty));
                                }
                            }
                        }
                        ++ cnt;
                    }
                }
            }
            
            if(!hasempty)
                return -1;
            for(int i = 0; i < n; ++ i){
                for(int j = 0; j < m; ++ j){
                    if(grid[i][j] == 0 && reachhousecnt[i][j] == houseTot){
                        ans = min(ans, mp[i][j]);
                        reachtoAllhouse = true;
                    }
                }
            }
            
            return ans == INT_MAX?-1:ans;
        }
    private:
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    };

Log in to reply
 

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