# Leetcode 317 Solution

https://leetcode.com/problems/shortest-distance-from-all-buildings

## 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;
}
};
``````