Last Updated: 20 Apr, 2021

Saving the city

Moderate

Asked in companies

Solve now

Problem statement

The avengers have the responsibility to save the world. To perform this task they have divided their responsibility such that each one takes the responsibility of one city. Mr. Stark aka Iron Man got the responsibility of the city Malibu. The only safe place in the city is the Stark tower. Now, Iron Man has to shift trapped people from different parts of the city to the Stark tower.

But he can only shift one person at a time. Due to less time he wants to take the shortest possible path. Help him to find the minimum distance that he had to cover to rescue all the trapped people.

Note:

1. Positions are represented by the cells in a 2D grid.
2. The positions of people don’t overlap.
3. Iron Man can move only up, down, left, and right to the adjacent cell.

Input Format

The first line contains a single integer ‘T’ representing the number of test cases. Then the test cases follow.

The first line of each test case contains two integers ‘HEIGHT’ and ‘WIDTH’ denoting the dimensions of the city. 

The second line contains two integers ‘X1’ and ‘Y1’ denoting the position of Stark Tower.

The third line contains two integers ‘X2’ and ‘Y2’ denoting the initial position of Iron Man.

The next line contains an integer ‘N’ denoting the number of trapped people.

The next ‘N’ line contains a 2D matrix ‘PERSONS’ of order ‘N’ x 2 denoting the position of ‘N’ people.

Output Format

 For each test case, print the minimum possible distance Iron Man has to cover.

 Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints

1 <= T <= 50
1 <= HEIGHT <= 10^4
1 <= WIDTH <= 10^4
3 <= HEIGHT * WIDTH <= 10^4
1 <= N <= 10^4
0 <= X1, X2 < HEIGHT
0 <= Y1, Y2 <  WIDTH
1 <= PERSONS[i][j] <= 10^4

Where ‘HEIGHT’ and ‘WIDTH’ are the dimensions of the city, ‘X1’, ‘Y1’ represents the position of the tower, ‘X2’, ‘Y2’ represents the position of Iron Man, ‘N’ represents the number of trapped people and ‘PERSONS[i][j]’ represents the position of trapped people.


Time limit: 1 sec

Solve now

Approaches

01 Approach

For rescuing trapped people firstly Iron Man will go to one person and shift him to the Stark Tower. Then move from Stark tower he will go to the next trapped person and shift him to the tower. After the first person, for every person, he is traveling the distance 2 * ‘D’ ( where ‘D’ be the distance between the tower and the person).

Here all people will be alike except the first one. So to minimize the distance covered, we need to find the person for which the value of ‘D’ - ‘X’ (where ‘D’ is the distance between the tower and the person, and ‘X’ be the distance between the person and Iron Man) is maximum.

Our final answer will be Σ 2* ‘Di’ - max (‘Di’ - ‘Xi’).

The steps are as follows:

In the ‘HELPER’ function
1. Find the distance between 2 points. This function will take ‘X1’, ‘Y1’, ‘X2’, ‘Y2’ as coordinates of 2 points.
2. Return the absolute value of (‘X1’ - ‘X2’) + absolute value of ( ‘Y1’ - ‘Y2’).
In the given function
1. Declare a variable ‘SUM’ to store the sum of the distance from the tower to the person. It will be of type int, and its initial value will be 0.
2. Declare another variable ‘MAX_DIFF’ to find the maximum value of the difference of distance from the tower to the person and the person to Iron man. It will be of type int and its initial value will be INT_MAX.
3. Now iterate on every person in the ‘PERSONS’ matrix. (say iterator be ‘i’ )
  1. Store the distance between the ‘i-th’ person and the tower in a temporary variable ‘DIST’
  2. Increase ‘SUM’ as ‘SUM’ += 2 * ‘DIST’
  3. Let's say the distance between the ‘i-th’ person and Iron Man is stored in a temporary variable ‘X’.
  4. Find the maximum value of the difference of distance between the tower and person and the person and Iron man, by maximizing the ‘MAX_DIFF’ as ‘MAX_DIFF’ = max(‘MAX_DIFF’, ‘DIST’ - ‘X’).
4. Return ‘SUM’ - ‘MAX_DIFF’

Solve now