Last Updated: 25 Jan, 2021

# Shortest Bridge

Moderate

## Problem statement

#### 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.
``````

## Approaches

### 01 Approach

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.

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).