50 lines Concise and easy understand c++ solution BFS


  • 0
    A
    class Solution {
    private:
        vector<pair<int, int>> dir{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public:
        int shortestDistance(vector<vector<int>>& grid) {
            if(grid.size() == 0 || grid[0].size() == 0) return -1;
            int m = grid.size(), n = grid[0].size();
            vector<vector<int>> visitedCount(grid.size(), vector<int>(grid[0].size(), 0));
            vector<pair<int, int>> buildings;
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(grid[i][j] == 1) buildings.push_back(make_pair(i, j));
                    grid[i][j] *= -1;
                }
            }
            for(int i = 0; i < buildings.size(); i++) {
                bfs(buildings[i], grid, visitedCount);
            }
            int result = INT_MAX;
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(grid[i][j] > 0 && visitedCount[i][j] == buildings.size()) {
                        result = min(grid[i][j], result);
                    }
                }
            }
            return result == INT_MAX ? -1 : result;
        }
        
        void bfs(pair<int, int> b, vector<vector<int>>& grid, vector<vector<int>>& visitedCount) {
            vector<vector<int>> dis(grid.size(), vector<int>(grid[0].size(), -1));
            queue<pair<int, int>> que;
            que.push(b);
            dis[b.first][b.second] = 0;
            visitedCount[b.first][b.second]++;
            while(!que.empty()) {
                pair<int, int> s = que.front();
                que.pop();
                for(int i = 0; i < 4; i++) {
                    int x = s.first + dir[i].first;
                    int y = s.second + dir[i].second;
                    if(x >= 0 && y >= 0 && x < grid.size() && y < grid[0].size()) {
                        if(grid[x][y] >= 0 && dis[x][y] < 0) {
                            dis[x][y] = dis[s.first][s.second] + 1;
                            visitedCount[x][y]++;
                            grid[x][y] += dis[x][y];
                            que.push(make_pair(x, y));
                        } 
                    }
                }
            }
        }
    };
    

Log in to reply
 

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