Meet-Up

Hard
0/120
Average time to solve is 35m
profile
Contributed by
6 upvotes
Asked in companies
FacebookMicrosoftOracle

Problem statement

Your friends live in a grid of size ‘N’ * ‘M’, where:

• Each ‘.’ represents an empty spot through which anyone can pass.

• Each ‘#’ represents an obstacle which no one can pass through.

• Each ‘F’ represents the house of your friend, and no one can pass through it.

You are planning to meet up with all your friends so you need to find an empty spot where you can wait for all your friends, and the sum of the total distance travelled by all your friends is minimum. Your friends can only move left, right, up or down, and each move increases the distance travelled by 1.

Find the minimum sum of total distance travelled by all your friends or print -1 to say that no such spot exists.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains two spaced integers, ‘N’ and ‘M’, denoting the number of rows and columns.

The following line ‘N’ lines contain a string of size ‘M’ denoting the grid where your friends live.
Output Format: 
For each test case, print a single integer denoting the minimum sum of distance your friends need to travel or -1 if there is no meeting spot.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
2 <= N, M <= 30 

Time Limit: 1 sec
Sample Input 1:
2
3 3
.#F
...
..F
3 3
.#F
..F
..F
Sample Output 1:
2
-1
Explanation for Sample Input 1:
In the first test case, you can wait at the point (1, 2), and your friends at the point (0,2) and (2,2) will have to cover the distance of unit 1. So the sum of total distance travelled by all your friends 2.

In the second test case, there is no spot where all three of your friends can meet as the friend at (0, 3) cant move.
Sample Input 2:
2
1 2 
F.
2 2 
.F
.F
Sample Output 2:
1 
3
Hint

Can we find the minimum distance of each empty spot to all your friends?

Approaches (1)
Breadth-First Search

We need to find a spot with the following two properties :

  1. The spot should be reachable by all your friends.
  2. The sum of the distance of that spot to all your friends is minimum.


 

We know, using BFS, we can find the shortest distance of all the spots from a single source. So we can treat each friend as a source and run a BFS to find the shortest distance of all the sports from that friend. 


 

Now, we will maintain two arrays for each spot, denoting the number of friends that can reach that spot and the sum of distance travelled by each friend. 


 

In the end, we need to find a spot where the count of friends that can reach that spot is equal to the total number of friends and store the minimum sum of distance travelled. 

 




 

Algorithm: 

  • Create a 2d array ‘totalDis’ of size ‘N’ * ‘M’ initialised to 0.
  • Create a 2d array ‘vis’ of size ‘N’ * ‘M’ initialised to 0.
  • Initialise ‘countFriends’ to 0.
  • Run a loop ‘i’ from 0 to ‘N’ - 1
    • Run a loop ‘j’ from 0 to ‘M’ - 1
      • If ‘grid[i][j]’ is equal to ‘F’, create a 2d array ‘dis’ initialised to -1 and run BFS to store the minimum distance from (i,j) to all the spots.
      • Increment ‘countFriends’ by 1.
      • Iterate through all the spots
        • If it is reachable from (i,j), i.e. ‘dis’ of that spot is not equal to -1, then increase ‘vis’ of that spot by 1 and add ‘dis’ of that spot to ‘totalDis’ of that spot.
  • Initialise ‘ans’ to -1.
  • Run a loop ‘i’ from 0 to ‘N’ - 1
    • Run a loop ‘j’ from 0 to ‘M’ - 1
      • If ‘vis[i][j]’ is equal to ‘countFriends’
        • If ‘ans’ is equal to -1 or ‘ans’ is greater than ‘totalDis[i][j]’, then update ‘ans’ to ‘totalDis[i][j]’.
  • Return ‘ans’.
Time Complexity

O((N * M) ^ 2), where ‘N’ is the number of rows and ‘M’ is the number of columns.


 

Each BFS call takes a time complexity of O(N * M), and we are going to call it for all the points having ‘F’. So total complexity is O( (count of ‘F’) * (N * M)) which is equivalent to O((N * M) * (N * M)).


 

Space Complexity

O(N * M), where ‘N’ is the number of rows, and ‘M’ is the number of columns.


 

We are using 2D arrays of size N * M to store the total distance from each friend, so space complexity becomes O(N * M).


 

Code Solution
(100% EXP penalty)
Meet-Up
Full screen
Console