Shortest Bridge
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.
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).
The idea here is to use the flood fill algorithm. We will keep filling all 4 directional neighbours with their current value + 1 until we hit another island. We can get the answer by picking a minimum from other islands' neighbours whose values are non-zero.
See below example for better understanding.
Suppose the islands given are
Now fill all the cells of island 2 by 2. Here Island 2 is a top-right brown colored island.
Now fill all the neighbors of 2 with 3
Now fill all the neighbors of 3 with 4.
Now fill all the neighbors of 4 with 5
Here, you easily get the shortest distance of the island colored in brown by checking all its neighbors having non-zero value. Here non - zero neighbours of 1 is 5.We need to subtract 2 from 5 as we have added 2 extra in the starting of flood fill algorithm by assigning all values of the island by 2. So, in the above case, the shortest bridge size will be 3.
The Algorithm is as follows:
- Declare a variable to store the length of the shortest bridge, say the ‘ANSWER’.
- We will use a 2-D ‘VISITED’ array to keep track of visited elements in ‘DFS’ function.
- Find a coordinate in the given array whose value is 1 and change all elements of the founded island to 2 by running a ‘DFS’.
- Call ‘FLOODFILL’ function to get the ‘ANSWER’.
- Subtract 2 from the ‘ANSWER’ as we have added 2 extra in the starting of flood fill algorithm by assigning all values of the island by 2.
- Finally, return the ‘ANSWER’.
Description of DFS function to set values of all elements of island2 to 2.
This function will take five arguments, ‘X’ and ‘Y’ denoting the current coordinates, a 2D array ‘VISITED’ to keep track of visited coordinates/nodes and a queue ‘Q’ to store all elements of the island
dfs(x, y, visited,q) :
- 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.
- If the element at ‘X’, ‘Y’ is not equal to 1 then return.
- Set the value of the element at ‘X’, ‘Y’ to 2.
- Add (‘X’, ’Y’) to queue for flood Fill.
- To check all the neighbors, recursively call in all 4 - directions. of (‘X’, ‘Y’) i.e. (‘X’ – 1, ‘Y’) , (‘X’ + 1, ‘Y’) , (‘X’, ‘Y’ –1) , (‘X’, ‘Y’ + 1).
Description of the Flood fill function.
This function will take four arguments, ‘A’ - denoting the given 2-D array, ’N’ - denoting the total number of rows, ‘M’ - denoting the total number of columns in the array and the queue ‘Q’ which stores all elements of island 2.
floodFill(a, n, m, q) :
- Declare a direction array to visit neighbours of (‘X’, ‘Y’) in all four directions i.e. (‘X’ – 1, ‘Y’) , (‘X’ + 1, ‘Y’) , (‘X’, ‘Y’ – 1) , (‘X’, ‘Y’ + 1).
- Declare a variable ‘VAL’ to maintain the current color value of neighbors.
- Run a loop until the queue is not empty.
- The size of the queue denotes the total number of nodes at the current level.
- Run a loop until you have visited all nodes of the current level.
- Pop the front item from the queue.
- Visit all 4 - directional neighbours of popped item i.e. (‘X’ – 1, ‘Y’) , (‘X’ + 1, ‘Y’) , (‘X’, ‘Y’ –1) , (‘X’, ‘Y’ + 1).
- Say, the neighbour of the popped element is (‘X’, ‘Y’).
- Check If the neighbour of (‘X’, ‘Y’) is out of bounds i.e. if x-coordinate does not lie between [0, ‘N’] or y-coordinate does not lie between [0, ‘M’].
- If the value at (‘X’, ‘Y’) < 1 then it means we have not visited this neighbour. So visit this neighbour.
- If a neighbour of (‘X’, ‘Y’) equals 1, Then it means we have found the second island. Now, Return the value at (‘X’, ‘Y’).
- Assign a new colour to the neighbour of (‘X’, ‘Y’).
- Push neighbour of (‘X’, ‘Y’)to queue.
- Increment value of ‘VAL’ by 1 for the next level.
In this solution, we will use BFS. We will use a similar idea as we used in the previous approach.
Since BFS is a level order traversal algorithm, we will first assign 2’s to one island using dfs then apply bfs on it. We will use a 2-D array to store the depth of nodes. We initialize the depth of all nodes to zero then we will update the depth of all unvisited neighbors by 1. If we encounter a neighbor having value 1 then we will return our answer as ‘DEPTH[CURNODE]’.
The Algorithm is as follows:
- Declare two 2-D arrays, one to keep track of visited elements ‘VISITED’ and the second one is to store the depth of the coordinates. Initialize both of them by zero.
- Declare an empty queue of pairs.
- Find a coordinate in the given array whose value is 1 and change all elements of the founded island to 2 by running a ‘DFS’ to it as done in the previous approach.
- Push the coordinates of the element found in the previous step.
- Declare a direction array to visit neighbors of (‘X’, ‘Y’) in all four directions i.e. (‘X’ – 1, ‘Y’) , (‘X’ + 1, ‘Y’) , (‘X’, ‘Y’ –1) , (‘X’, ‘Y’ + 1).
- Run a loop until the queue is not empty.
- Pop the front item from the queue and mark it as visited true.
- Visit all 4 - directional neighbors of the popped item i.e. (‘X’ – 1, ‘Y’) , (‘X’ + 1, ‘Y’) , (‘X’, ‘Y’ –1) , (‘X’, ‘Y’ + 1).
- Say, the neighbor of the popped element is (‘X’, ‘Y’).
- 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 continue.
- If (‘X’, ‘Y’) is visited then continue.
- If (‘X’, ‘Y’) is equal to 1, then return ‘DEPTH’ of the popped item.
- Else assign ‘DEPTH[X][Y]’ as the depth of popped item + 1 and push (‘X’, ‘Y’) to queue.
