Last Updated: 2 Nov, 2021
Meet-Up
Hard
Asked in companies
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.
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
Approaches
We need to find a spot with the following two properties :
- The spot should be reachable by all your friends.
- 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.
- Run a loop ‘j’ from 0 to ‘M’ - 1
- 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]’.
- If ‘vis[i][j]’ is equal to ‘countFriends’
- Run a loop ‘j’ from 0 to ‘M’ - 1
- Return ‘ans’.