Shortest Distance from All Buildings in C++

Suppose we want to make a house on an empty land which reaches all buildings in the shortest amount of distance. We can only move four directions like up, down, left and right. We have a 2D grid of values 0, 1 or 2, where −

• 0 represents an empty land which we can pass by freely.

• 1 represents a building which we cannot pass through.

• 2 represents an obstacle which we cannot pass through.

So, if the input is like

then the output will be 7 as Given three buildings are present at (0,0), (0,4), (2,2), and an obstacle is at (0,2) so the point (1,2) is an ideal empty land to build a house, as the total travel distance is 3+3+1=7 is minimum.

To solve this, we will follow these steps −

• ret := inf

• n := row size of grid

• m := col size of grid

• numberOfOnes := 0

• Define one 2D array dist of size n x m

• Define one 2D array reach of size n x m

• for initialize i := 0, when i < n, update (increase i by 1), do −

  • for initialize j := 0, when j < m, update (increase j by 1), do −

    • if grid[i, j] is same as 1, then −

      • (increase numberOfOnes by 1)

      • Define one queue q

      • insert {i, j} into q

      • Define one set visited

      • for initialize lvl := 1, when not q is empty, update (increase lvl by 1), do −

        • sz := size of q

        • while sz is non-zero, decrease sz in each iteration, do −

          • curr := first element of q

          • delete element from q

          • x := curr.first

          • y := curr.second

          • for initialize k := 0, when k < 4, update (increase k by 1), do −

            • nx := x + dir[k, 0]

            • ny := y + dir[k, 1]

            • if nx and ny are in range of grid or grid[nx,ny] is not 0, then

            • Ignore following part, skip to the next iteration

            • insert {nx, ny} into visited

            • dist[nx, ny] := dist[nx, ny] + lvl

            • (increase reach[nx, ny] by 1)

            • insert {nx, ny} into q

• for initialize i := 0, when i < n, update (increase i by 1), do −

  • for initialize j := 0, when j < m, update (increase j by 1), do −

    • if grid[i, j] is same as 0 and reach[i, j] is same as numberOfOnes, then −

      • ret := minimum of ret and dist[i, j]

• return (if ret is same as inf, then -1, otherwise ret)

Example  

Let us see the following implementation to get better understanding −

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; class Solution { public:    int shortestDistance(vector<vector<int>>& grid) {       int ret = INT_MAX;       int n = grid.size();       int m = grid[0].size();       int numberOfOnes = 0;       vector < vector <int> > dist(n, vector <int>(m));       vector < vector <int> > reach(n, vector <int>(m));       for(int i = 0; i < n; i++){          for(int j = 0; j < m; j++){             if(grid[i][j] == 1){                numberOfOnes++;                queue < pair <int, int> > q;                q.push({i, j});                set < pair <int, int> > visited;                for(int lvl = 1; !q.empty(); lvl++){                   int sz = q.size();                   while(sz--){                      pair <int, int> curr = q.front();                      q.pop();                      int x = curr.first;                      int y = curr.second;                      for(int k = 0; k < 4; k++){                         int nx = x + dir[k][0];                         int ny = y + dir[k][1];                         if(nx < 0 || ny < 0 || nx >= n || ny >= m || visited.count({nx, ny}) || grid[nx][ny] != 0) continue;                         visited.insert({nx, ny});                         dist[nx][ny] += lvl;                         reach[nx][ny]++;                         q.push({nx, ny});                      }                   }                }             }          }       }       for(int i = 0; i < n; i++){          for(int j = 0; j < m; j++){             if(grid[i][j] == 0 && reach[i][j] == numberOfOnes){                ret = min(ret, dist[i][j]);             }          }       }       return ret == INT_MAX ? -1 : ret;    } };

Input

[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

Output

7