Leetcode 317 Solution

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0)
            return -1;

        int m = grid.size();
        int n = grid[0].size();

        int building_cnt = 0;

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                building_cnt += grid[i][j] == 1;

        vector<vector<int>> total_dist(m, vector<int>(n));

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] != 1)
                    continue;

                queue<pair<int, int>> q;
                q.push(make_pair(i, j));

                vector<vector<int>> dist(m, vector<int>(n, -1));
                int hit_building = 0;
                dist[i][j] = 0;

                while (q.empty() == false)
                {
                    auto pos = q.front();
                    q.pop();

                    int y = pos.first;
                    int x = pos.second;

                    if (grid[y][x] == 1)
                        hit_building++;

                    if ((y != i || x != j) && grid[y][x] != 0)
                        continue;

                    if (y > 0 && dist[y - 1][x] == -1)
                    {
                        dist[y - 1][x] = dist[y][x] + 1;
                        q.push(make_pair(y - 1, x));
                    }

                    if (y < m - 1 && dist[y + 1][x] == -1)
                    {
                        dist[y + 1][x] = dist[y][x] + 1;
                        q.push(make_pair(y + 1, x));
                    }

                    if (x > 0 && dist[y][x - 1] == -1)
                    {
                        dist[y][x - 1] = dist[y][x] + 1;
                        q.push(make_pair(y, x - 1));
                    }

                    if (x < n - 1 && dist[y][x + 1] == -1)
                    {
                        dist[y][x + 1] = dist[y][x] + 1;
                        q.push(make_pair(y, x + 1));
                    }
                }

                if (hit_building != building_cnt)
                    return -1;

                for (int y = 0; y < m; y++)
                    for (int x = 0; x < n; x++)
                        if (grid[y][x] == 0)
                        {
                            if (dist[y][x] == -1 || total_dist[y][x] == INT_MAX)
                                total_dist[y][x] = INT_MAX;
                            else
                                total_dist[y][x] += dist[y][x];
                        }
            }
        }

        int min_val = INT_MAX;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 0)
                    min_val = min(min_val, total_dist[i][j]);

        return min_val == INT_MAX ? -1 : min_val;
    }
};