**Difficulty: Hard**

**Frequency: N/A**

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. 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.

The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x – p1.x| + |p2.y – p1.y|.

For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 – 0 – 2 – 0 – 1

| | | | |

0 – 0 – 0 – 0 – 0

| | | | |

0 – 0 – 1 – 0 – 0

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.

**My solution:**

**Data structure:**

**Steps:**

**Complexity:**

Runtime:

Space:

**Test cases:**

**Corner cases:**

**Code:**

class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
if (grid.empty()) return 0;
int m = grid.size(), n = grid[0].size();
int nb = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) nb++;
}
}
int result = INT_MAX;
bool found = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) continue;
int dist = 0, cnt = 0;
vector<int> start = {i, j, 0};
queue<vector<int>> myQ;
myQ.push(start);
vector<vector<bool>> visited = (m, vector<int>(n, false));
visited[i][j] = true;
while (!myQ.empty()) {
int p = myQ.front()[0];
int q = myQ.front()[1];
int steps = myQ.front()[2];
myQ.pop();
if (grid[p][q] == 1) {
cnt++;
dist += steps;
}
if (grid[p][q] == 0 || (p == i) && (q == j)) {
if (p - 1 >= 0 && grid[p - 1][q] > 2 && !visisted[p - 1][q]) {
vector<int> tmp = {p - 1, q, steps + 1};
myQ.push(tmp);
visited[p - 1][q] = true;
}
if (p + 1 < m && grid[p + 1][q] > 2 && !visisted[p + 1][q]) {
vector<int> tmp = {p + 1, q, steps + 1};
myQ.push(tmp);
visited[p + 1][q] = true;
}
if (q - 1 >= 0 && grid[p][q - 1] > 2 && !visisted[p][q - 1]) {
vector<int> tmp = {p, q - 1, steps + 1};
myQ.push(tmp);
visited[p][q - 1] = true;
}
if (q + 1 < n && grid[p][q + 1] > 2 && !visisted[p][q + 1]) {
vector<int> tmp = {p, q + 1, steps + 1};
myQ.push(tmp);
visited[p][q + 1] = true;
}
}
}
if (grid[i][j] == 1 && cnt < nb) return -1;
if (grid[i][j] == 0 && cnt == nb) {
found = true;
result = min(disk, result);
}
}
}
return found ? result : -1;
}
}

**Another solution:**

**Data structure:**

**steps:**

**Complexity**:

**Code**:

**Things to learn:**