Shortest Bridge

Posted: 25 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Every story has an Endgame. This is another such story.

Tony Stark and Thanos live in two different islands. Tony wants to reach Thanos's island in minimum time to save the world.

You are given a 2-D binary array of 'N' rows and 'M' columns. If the element of the array is 1 it means it has land in there else if the element is 0 means it has water in there. There are exactly two islands in this array. In one island Tony lives and in another island, Thanos lives. An island is a 4 – directionally connected component of 1’s.

For example

In the above figure, there are two islands coloured in brown and orange respectively.

Tony wants to build a bridge between these two islands. With the help of Friday Tony can build the bridge by changing 1 or more 0’s to 1’s. Size of the bridge is the number of 0’s changed to 1’s. Tony wants to minimize the size of the bridge as it minimizes time to reach Thanos.

For example

Here Bridge is marked in red colour and 1 is the minimum size of bridge possible.

Tony is busy assembling all the avengers, so he called you to solve this problem.

Input Format
The first line of input contains an integer 'T' representing the number of test cases. Then the 'T' test cases are as follows.

The first line of each test case contains two single-spaced integers ‘N’ and ‘M’, representing the number of rows and columns of the 2-D array, respectively.

For the next 'N' lines, each line contains 'M' space-separated integers (0 or 1), where 0 denotes the water and 1 denotes the land.
Output Format:
For each test case, print the length of the shortest bridge which connects the two islands.

The output for each test case is printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N, M <= 100
0 <= ARR[i][j] <= 1

Where ‘ARR[i][j]’ is the value of the elements of the 2-D array.

Time Limit: 1 sec.
Approach 1

In this solution, we will first store all coordinates of both the islands in two vectors of pairs using dfs. Then we will generate all pairs of coordinates between the two islands and find a pair of coordinates having a minimum distance between them.

 

The Algorithm is as follows: 

  1. Declare a variable to store the length of the shortest bridge, say the 'ANSWER'.
  2. We will assign the maximum size of the bridge i.e. ‘N’ * ’M’ to the 'ANSWER'.
  3. We will maintain a 2D visited array to keep track of visited elements in ‘DFS’ function.
  4. Run a ‘DFS’ to store all coordinates of island1 and island2 in two vectors of pairs, say 'ISLAND1' and 'ISLAND2'.
  5. Run a loop and iterate over all coordinates of island1, say ‘X1’ and ‘Y1’.
  6. Run another loop and iterate over all coordinates of island2, say ‘X2’ and ‘Y2’.
  7. Distance between (‘X1’, ‘Y1’) and (‘X2’, ‘Y2’) is abs(‘X1’ – ‘X2’) + abs(‘Y1’ – ‘Y2’) – 1. So if the distance is less than the 'ANSWER' then we will update the 'ANSWER' with distance.
  8. Finally, return the 'ANSWER'.

 

Description of DFS function to store coordinates of island1 and island2.

This function will take four arguments, ‘X’ and ‘Y’ denoting the current coordinates, a 2-D array ‘VISITED’ to keep track of visited coordinates/nodes and a pair of arrays/vectors to store coordinates of the current island.

DFS(X, Y, VISITED, CURISLAND) : 

  1. If ‘X’, ‘Y’ is out of bounds i.e. if ‘X’ does not lie between [0, ‘N’] or ‘Y’ does not lie between [0, ‘M’] then return.
  2. If ‘VISITED[X][Y]’ is true then return IT.
  3. If the element at ‘X’, ‘Y’ is not equal to 1 then return.
  4. Add ‘X’, ‘Y’ to curIsland.
  5. Add (‘X’, ‘Y’) to the island and mark ‘VISITED[X][Y]’ as true.
  6. Visit all the neighbors by recursively calling in all 4 - directions of (‘X’, ‘Y’) i.e. (‘X’ – 1, ‘Y’) , (‘X’ + 1, ‘Y’) , (‘X’, ‘Y’ –1) , (‘X’, ‘Y’ + 1).
Try Problem