Best meeting point in 2D binary array | C ++ program to find best meeting point in 2D array ; Find all members home 's position ; Sort positions so we can find most beneficial point ; middle position will always beneficial for all group members but it will be sorted which we have already done ; Now find total distance from best meeting point ( x , y ) using Manhattan Distance formula ; Driver program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ROW  3 NEW_LINE #define COL  5 NEW_LINE int minTotalDistance ( int grid [ ] [ COL ] ) { if ( ROW == 0 COL == 0 ) return 0 ; vector < int > vertical ; vector < int > horizontal ; for ( int i = 0 ; i < ROW ; i ++ ) { for ( int j = 0 ; j < COL ; j ++ ) { if ( grid [ i ] [ j ] == 1 ) { vertical . push_back ( i ) ; horizontal . push_back ( j ) ; } } } sort ( vertical . begin ( ) , vertical . end ( ) ) ; sort ( horizontal . begin ( ) , horizontal . end ( ) ) ; int size = vertical . size ( ) / 2 ; int x = vertical [ size ] ; int y = horizontal [ size ] ; int distance = 0 ; for ( int i = 0 ; i < ROW ; i ++ ) for ( int j = 0 ; j < COL ; j ++ ) if ( grid [ i ] [ j ] == 1 ) distance += abs ( x - i ) + abs ( y - j ) ; return distance ; } int main ( ) { int grid [ ROW ] [ COL ] = { { 1 , 0 , 1 , 0 , 1 } , { 0 , 1 , 0 , 0 , 0 } , { 0 , 1 , 1 , 0 , 0 } } ; cout << minTotalDistance ( grid ) ; return 0 ; }