A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using , where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0), (0,4), and (2,2):

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

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

class Solution {public:    int minTotalDistance(vector
     
      
       >& grid) {        vector
       
         row;        vector
        
          col;        for(int i = 0;i
         

> &distance,vector

> &counts,vector

>& grid) { int m = grid.size(); int n = grid[0].size(); vector

> visited(m,vector

(n,false)); visited[i][j] = true; counts[i][j] +=1; queue

> q; vector

> dirs = { {-1,0},{ 1,0},{ 0,-1},{ 0,1}}; q.push({i,j}); int step = 0; while(!q.empty()) { int N = q.size(); step++; for(int i = 0;i

=m || nextc<0 || nextc>=n || visited[nextr][nextc]) continue; visited[nextr][nextc] = true; q.push({nextr,nextc}); distance[nextr][nextc]+=step; counts[nextr][nextc]+=1; } } } } };