317. Shortest Distance from All Buildings

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

• Each 0 marks an empty land which you can pass by freely.
• Each 1 marks a building which you cannot pass through.
• Each 2 marks an obstacle which you cannot pass through.

Example:

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 7 

Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2),
             the point (1,2) is an ideal empty land to build a house, as the total 
             travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

class Solution {

public:

    int shortestDistance(vector<vector<int>>& grid) {

        vector<vector<int>> ans (grid.size(), vector<int>(grid[0].size(), 0));

        vector<vector<int>> nums (grid.size(), vector<int>(grid[0].size(), 0));

        

        int row = grid.size();

        int col = grid[0].size();

        

        int buildingCount = 0;

        for (int i = 0; i < row; i++) {

            for (int j = 0; j < col; j++) {

                if (grid[i][j] == 1) {

                    buildingCount++;

                    vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));

                    bfs(grid, i, j, 0, visited, ans, nums);

                }

            }

        }

        

        int dist = INT_MAX;

        for (int i = 0; i < row; i++) {

            for (int j = 0; j < col; j++) {

                if (ans[i][j] != 0 && nums[i][j] == buildingCount) {

                    dist = min(dist, ans[i][j]);

                }

            }

        }

        return (dist == INT_MAX ? -1 : dist);

    }

    

    void bfs(vector<vector<int>>& grid, int x, int y, int dist,

             vector<vector<bool>>& visited, vector<vector<int>>& ans,

            vector<vector<int>>& nums) {

        queue<pair<int, pair<int,int>>> q;

        q.push(make_pair(dist, make_pair(x,y)));

         visited[x][y] = true;

        while (!q.empty()) {

            pair<int, pair<int, int>> node = q.front(); q.pop();

            ans[node.second.first][node.second.second] += node.first;

            

            vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

            

            for (auto dir : dirs) {

                int i = node.second.first + dir[0];

                int j = node.second.second + dir[1];

                if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() ||

                   visited[i][j] || grid[i][j] == 2 || grid[i][j] == 1) {

                    continue;

                }

                visited[i][j] = true;

                nums[i][j]++;

                q.push(make_pair(node.first + 1, make_pair(i, j)));

            }

        }

    }

};