Shortest Bridge

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.

Test Case 1: Cells of the bridge are marked using B. 0 1 0 0 0 B 0 0 0 1 0 0 1 1 1 1 Here the minimum size of the bridge is 1. So, the answer is 1. Note: Below shown bridge is also a valid bridge but its size is 3 which is not minimum. 0 1 B 0 0 0 B 0 0 1 B 0 1 1 1 1 Test Case 2: Cells of the bridge are marked using B. 1 1 0 1 0 0 B B 1 Here the minimum size of the bridge is 2. So, the answer is 2.

Brute Force

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:

Declare a variable to store the length of the shortest bridge, say the 'ANSWER'.
We will assign the maximum size of the bridge i.e. ‘N’ * ’M’ to the 'ANSWER'.
We will maintain a 2D visited array to keep track of visited elements in ‘DFS’ function.
Run a ‘DFS’ to store all coordinates of island1 and island2 in two vectors of pairs, say 'ISLAND1' and 'ISLAND2'.
Run a loop and iterate over all coordinates of island1, say ‘X1’ and ‘Y1’.
Run another loop and iterate over all coordinates of island2, say ‘X2’ and ‘Y2’.
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.
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) :

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.
If ‘VISITED[X][Y]’ is true then return IT.
If the element at ‘X’, ‘Y’ is not equal to 1 then return.
Add ‘X’, ‘Y’ to curIsland.
Add (‘X’, ‘Y’) to the island and mark ‘VISITED[X][Y]’ as true.
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).

Time Complexity

O((N ^ 2) * (M ^ 2)), where ‘N’ is the total number of rows and M is the total number of columns in the given 2-D array.

In the worst-case, both island1 and island2 can have O(N * M) coordinates. Storing coordinates of island1 and island2 using dfs takes O(N * M) time. Also, we are generating all combination of coordinates between island1 and island2 that will take O(N * M) * O(N * M) = O((N ^ 2) * (M ^ 2)) time.

Hence, the overall time complexity will be O((N ^ 2) * (M ^ 2)).

Space Complexity

O(N * M), where ‘N’ is the total number of rows and ‘M’ is the total number of columns in the given 2-D array.

We are storing all coordinates of both islands which will take O(N * M) space in the worst case. Also, we are using a 2-D visited array which will take O(N * M) space. Also, our dfs function requires O(N * M) stack space in the recursive calls.

Hence, the overall space complexity will be O(N * M) + O(N * M) + O(N * M) = O(N * M).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation For Sample Input 1:

Sample Input 2:

Sample Output 2:

Explanation For Sample Input 2: