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

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

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

/*
    Time Complexity  : 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.
*/

import javafx.util.Pair;
import java.util.ArrayList;

public class Solution {

    // Dfs function to store coordinates of island1 and island2.
    public static void dfs(int x, int y, ArrayList> arr, boolean[][] visited, ArrayList> curIsland) {
        int rowSize = visited.length, columnSize = visited[0].length;

        if (x < 0 || x >= rowSize || y < 0 || y >= columnSize) {
            return;
        }

        if (visited[x][y] == true) {
            return;
        }

        if (arr.get(x).get(y) != 1) {
            return;
        }

        // curIsland.push_back({x,y});
        curIsland.add( new Pair(x,y));
        visited[x][y] = true;

        // Visit all the neighbours by recursively calling in all 4 - directions.
        dfs(x - 1, y, arr, visited, curIsland);
        dfs(x + 1, y, arr, visited, curIsland);
        dfs(x, y - 1, arr, visited, curIsland);
        dfs(x, y + 1, arr, visited, curIsland);
    }

    public static int shortestBridge(ArrayList> arr, int n, int m) {
        int answer = n * m;

        /*
            Declare a 2D visited array to keep track of the visited 
            elements in dfs function.
        */
        boolean[][] visited = new boolean[n][m];
        for(int i=0;i            for(int j=0;j                visited[i][j] = false;
            }
        }

        ArrayList> island1 = new ArrayList>();
        ArrayList> island2 = new ArrayList>();

        // Run a dfs to store all coordinates of island1 and island2.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr.get(i).get(j) == 1 && visited[i][j] == false) {
                    if (island1.size() == 0) {
                        dfs(i, j, arr, visited, island1);
                    } else {
                        dfs(i, j, arr, visited, island2);
                    }
                }
            }
        }

        for (int i = 0; i < island1.size(); i++) {
            for (int j = 0; j < island2.size(); j++) {
                int x1, y1, x2, y2;
                x1 = island1.get(i).getKey();
                y1 = island1.get(i).getValue();
                x2 = island2.get(j).getKey();
                y2 = island2.get(j).getValue();

                /*
                    If the distance between (x1, y1) and (x2, y2) is less than the answer
                    Then we will update the answer with this distance.
                */
                int distance = Math.abs(x1 - x2) + Math.abs(y1 - y2) - 1;
                answer = Math.min(answer, distance);
            }
        }

        return answer;
    }
}

/*
    Time Complexity  : 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.
*/

// Dfs function to store coordinates of island1 and island2.
void dfs(int x, int y, vector < vector < int >> & arr, vector < vector < bool >> & visited, vector < pair < int, int >> & curIsland) {
    int rowSize = visited.size(), columnSize = visited[0].size();

    if (x < 0 or x >= rowSize or y < 0 or y >= columnSize) {
        return;
    }

    if (visited[x][y] == true) {
        return;
    }

    if (arr[x][y] != 1) {
        return;
    }

    curIsland.push_back({x,y});
    visited[x][y] = true;

    /*
        Visit all the neighbours by recursively calling in all 4 - directions of
        (x, y) i.e. (x – 1, y) , (x + 1, y) , (x, y–1) , (x, y + 1).
    */
    dfs(x - 1, y, arr, visited, curIsland);
    dfs(x + 1, y, arr, visited, curIsland);
    dfs(x, y - 1, arr, visited, curIsland);
    dfs(x, y + 1, arr, visited, curIsland);
}

int shortestBridge(vector < vector < int >> & arr, int n, int m) {
    int answer = n * m;

    /*
        Declare a 2D visited array to keep track of the visited 
        elements in dfs function.
    */
    vector < vector < bool >> visited(n, vector < bool > (m, false));

    vector < pair < int, int >> island1, island2;

    // Run a dfs to store all coordinates of island1 and island2.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 1 and visited[i][j] == false) {
                if (island1.size() == 0) {
                    dfs(i, j, arr, visited, island1);
                } else {
                    dfs(i, j, arr, visited, island2);
                }
            }
        }
    }

    for (int i = 0; i < island1.size(); i++) {
        for (int j = 0; j < island2.size(); j++) {
            int x1, y1, x2, y2;
            x1 = island1[i].first;
            y1 = island1[i].second;
            x2 = island2[j].first;
            y2 = island2[j].second;

            /*
                If the distance between (x1, y1) and (x2, y2) is less than the answer
                Then we will update the answer with this distance.
            */
            int distance = abs(x1 - x2) + abs(y1 - y2) - 1;
            answer = min(answer, distance);
        }
    }

    return answer;
}

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:

1. Declare a variable to store the length of the shortest bridge, say the ‘ANSWER’.
2. We will use a 2-D ‘VISITED’ array to keep track of visited elements in ‘DFS’ function.
3. 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’.
4. Call ‘FLOODFILL’ function to get the ‘ANSWER’.
5. 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.
6. 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) : 

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.
3. If the element at ‘X’, ‘Y’ is not equal to 1 then return.
4. Set the value of the element at ‘X’, ‘Y’ to 2.
5. Add (‘X’, ’Y’) to queue for flood Fill.
6. 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) :

1. 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).
2. Declare a variable ‘VAL’ to maintain the current color value of neighbors.
3. 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.
4. Pop the front item from the queue.
5. Visit all 4 - directional neighbours of popped item i.e. (‘X’ – 1, ‘Y’) , (‘X’ + 1, ‘Y’) , (‘X’, ‘Y’ –1) , (‘X’, ‘Y’ + 1).
6. Say, the neighbour of the popped element is (‘X’, ‘Y’).
7. 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’].
8. If the value at (‘X’, ‘Y’) < 1 then it means we have not visited this neighbour. So visit this neighbour.
9. If a neighbour of (‘X’, ‘Y’) equals 1, Then it means we have found the second island. Now, Return the value at (‘X’, ‘Y’).
10. Assign a new colour to the neighbour of (‘X’, ‘Y’).
11. Push neighbour of (‘X’, ‘Y’)to queue.
12. Increment value of ‘VAL’ by 1 for the next level.

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.

In the worst case, both dfs requires O(N * M) stack space in the form of recursive calls. Also, we are using one extra 2-D array, visited that will take O(N * M) space. Also, there can be O(N * M) elements in the queue in the worst case. Hence the overall space complexity will be O(N * M) + O(N * M) + O(N * M) = O(N * M).

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.

In the worst-case, both dfs and flood fill function takes O(N * M) time as we need to visit O(N * M) elements. Hence the overall time complexity will be O(N * M).

'''
    Time Complexity  : O(N * M)
    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.
'''

from collections import deque

# Dfs function to assign 2 to all elements of island 1.
def dfs(x, y, arr, visited, q):
    
    rowSize = len(visited)
    columnSize = len(visited[0])
    
    if (x < 0 or x >= rowSize or y < 0 or y >= columnSize):
        return
    
    if (visited[x][y] == True):
        return
    
    if (arr[x][y] != 1):
        return
    
    visited[x][y] = True
    
    arr[x][y] = 2
    
    q.append((x, y))
    
    dfs(x - 1, y, arr, visited, q)
    dfs(x + 1, y, arr, visited, q)
    dfs(x , y - 1, arr, visited, q)
    dfs(x, y + 1, arr, visited, q)


# Flood Fill function to get length of shortest bridge.
def floodFill(arr, n, m, q):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    # Val will denote current color value of the neighbour.
    val = 3
    
    while (len(q) > 0):
        curLevelSize = len(q)
        
        while curLevelSize:
    
            frontNode = q.popleft()
            x = frontNode[0]
            y = frontNode[1]
            
            for i in range(4):
                newX = x + dx[i]
                newY = y + dy[i]
                
                # Check if we have visited it before or not.
                if newX >= 0 and newX < n and newY >= 0 and newY < m:

                    if arr[newX][newY] <= 1:
                        '''
                            If neighbour of (x,y) equals 1
                            Then we have found the second island
                            Now, Return the value at (x, y).
                        '''
                        if arr[newX][newY] == 1:
                            return arr[x][y]
                    
                        q.append((newX, newY))
                        arr[newX][newY] = val
                    
            curLevelSize -= 1
            
        val += 1


def shortestBridge(arr, n, m):

    # Declare a 2D visited array to keep track of the visited elements in dfs function.
    visited = [[False for i in range(m)] for j in range(n)]
    depths = [[0 for i in range(m)] for j in range(n)]
    q = deque()
    
    found = 0;

    # Run two nested loops to find first island.
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1:
                dfs(i, j, arr, visited, q);
                found = 1;
                break;
        if (found):
            break
                   
    answer = floodFill(arr, n, m, q)
    answer = answer - 2
    
    return answer              
    

/*
    Time Complexity  : O(N * M)
    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
*/

#include 

// Dfs function to assign 2 to all elements of island 1.
void dfs(int x, int y, vector < vector < int >> & arr, vector < vector < bool >> & visited, queue < pair < int, int >> & q) {
    int rowSize = visited.size(), columnSize = visited[0].size();

    if (x < 0 or x >= rowSize or y < 0 or y >= columnSize) {
        return;
    }

    if (visited[x][y] == true) {
        return;
    }

    if (arr[x][y] != 1) {
        return;
    }

    visited[x][y] = true;
    arr[x][y] = 2;

    q.push({x,y});

    /*
         To check all the neighbours, recursively call in all 4 - directions of
         (x, y) i.e. (x – 1, y) , (x + 1, y) , (x, y–1) , (x, y + 1).
    */
    dfs(x - 1, y, arr, visited, q);
    dfs(x + 1, y, arr, visited, q);
    dfs(x, y - 1, arr, visited, q);
    dfs(x, y + 1, arr, visited, q);
}

// Flood Fill function to get length of shortest bridge.
int floodFill(vector < vector < int >> & arr, int n, int m, queue < pair < int, int >> & 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).
    */
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};

    // Val will denote current color value of neighbours
    int val = 3;

    while (!q.empty()) {
        int curLevelSize = q.size();

        // Visit all neighbours of current level
        while (curLevelSize--) {
            pair < int, int > frontNode = q.front();
            q.pop();

            int x = frontNode.first, y = frontNode.second;

            for (int i = 0; i < 4; i++) {
                int newX = frontNode.first + dx[i], newY = frontNode.second + dy[i];

                if (newX >= 0 and newX < n and newY >= 0 and newY < m) {
                    // Check if we have visited it before or not
                    if (arr[newX][newY] <= 1) {
                        /*
                            If neighbour of (x,y) equals 1
                            Then we have found the second island
                            Now, Return the value at (x, y).
                        */
                        if (arr[newX][newY] == 1) {
                            return arr[x][y];
                        }

                        arr[newX][newY] = val;

                        q.push({newX,newY});
                    }
                }
            }
        }
        
        val++;
    }

}
int shortestBridge(vector < vector < int >> & arr, int n, int m) {
    int answer;

    vector < vector < bool >> visited(n, vector < bool > (m, false));

    queue < pair < int, int >> q;

    bool found = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {

            // If arr[i][j] = 1 means we have found an island.
            if (arr[i][j] == 1) {

                // Run a dfs to change all elements of this island to 2.
                dfs(i, j, arr, visited, q);

                found = 1;
                break;
            }
        }

        if (found) {
            break;
        }
    }

    answer = floodFill(arr, n, m, q);

    /*
         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.
    */
    answer = answer - 2;

    return answer;
}

/*
    Time Complexity  : O(N * M)
    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.
*/

import java.util.Queue;
import java.util.LinkedList;
import javafx.util.Pair;
import java.util.ArrayList;

public class Solution {

    public static void dfs(int x, int y, ArrayList> arr, boolean[][] visited, Queue> q) {
        int rowSize = visited.length, columnSize = visited[0].length;

        if (x < 0 || x >= rowSize || y < 0 || y >= columnSize) {
            return;
        }

        if (visited[x][y] == true) {
            return;
        }

        if (arr.get(x).get(y) != 1) {
            return;
        }

        visited[x][y] = true;
        ArrayList updatedArrayList = arr.get(x);
        updatedArrayList.set(y,2);
        arr.set(x,updatedArrayList);

        q.add(new Pair(x,y));

        // To check all the neighbours, recursively call in all 4 - directions.  
        dfs(x - 1, y, arr, visited, q);
        dfs(x + 1, y, arr, visited, q);
        dfs(x, y - 1, arr, visited, q);
        dfs(x, y + 1, arr, visited, q);
    }

    // Flood Fill function to get length of shortest bridge.
    public static int floodFill( ArrayList> arr, int n, int m, Queue> q) {
        
        // Declare a direction array to visit neighbours of (x,y) in all four directions.
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        // Val will denote current color value of neighbours.
        int val = 3;

        while (q.size() > 0) {
            int curLevelSize = q.size();

            // Visit all neighbours of current level.
            while (curLevelSize-- > 0) {
                Pair < Integer, Integer > frontNode = q.remove();

                int x = frontNode.getKey(), y = frontNode.getValue();

                for (int i = 0; i < 4; i++) {
                    int newX = frontNode.getKey() + dx[i], newY = frontNode.getValue() + dy[i];

                    if (newX >= 0 && newX < n && newY >= 0 && newY < m) {

                        // Check if we have visited it before or not.
                        if (arr.get(newX).get(newY) <= 1) {
                            /*
                                If neighbour of (x,y) equals 1
                                Then we have found the second island
                                Now, Return the value at (x, y).
                            */
                            if (arr.get(newX).get(newY) == 1) {
                                return arr.get(x).get(y);
                            }

                            ArrayList updatedArrayList = arr.get(newX);
                            updatedArrayList.set(newY,val);
                            arr.set(newX,updatedArrayList);

                            q.add(new Pair(newX,newY));
                        }
                    }
                }
            }

            val++;
        }

        return 0;
    }

    public static int shortestBridge(ArrayList> arr, int n, int m) {
        int answer = 0;

        boolean[][] visited = new boolean[n][m];
        for(int i=0;i            for(int j=0;j                visited[i][j] = false;
            }
        }

        Queue> q = new LinkedList<>();

        boolean found = false;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                // If arr[i][j] = 1 means we have found an island.
                if (arr.get(i).get(j) == 1) {

                    // Run a dfs to change all elements of this island to 2.
                    dfs(i, j, arr, visited, q);

                    found = true;
                    break;
                }
            }
            
            if (found) {
                break;
            }
        }

        answer = floodFill(arr, n, m, q);

        /*
             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.
        */
        answer = answer - 2;

        return answer;
    }
}

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:

1. 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.
2. Declare an empty queue of pairs.
3. 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.
4. Push the coordinates of the element found in the previous step.
5. 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).
6. 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.

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.

In the worst case, the dfs function requires O(N * M) stack space in the form of recursive calls. Also, there can be O(N * M) elements in the queue in the worst case. Also, we are using two extra 2-D arrays, visited and depth. Both of them take O(N*M) space. Hence, the overall space complexity will be O(N * M) + O(N * M) + O(N * M) + O(N * M) = O(N * M).

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.

In the worst-case, dfs function takes O(N * M) time as there can be O(N * M) coordinates in island2. Also, our BFS takes O(N * M) time as we need to visit O(N * M) coordinates in the worst case. Hence the overall time complexity will be O(N * M) + O(N * M) = O(N * M).

'''
    Time Complexity  : O(N * M)
    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.
'''

from collections import deque

# Dfs function to assign 2 to all elements of island 1.
def dfs(x, y, arr, visited, q):
    
    rowSize = len(visited)
    columnSize = len(visited[0])
    
    if (x < 0 or x >= rowSize or y < 0 or y >= columnSize):
        return
    
    if (visited[x][y] == True):
        return
    
    if (arr[x][y] != 1):
        return
    
    visited[x][y] = True
    
    arr[x][y] = 2
    
    q.append((x, y))
    
    dfs(x - 1, y, arr, visited, q)
    dfs(x + 1, y, arr, visited, q)
    dfs(x , y - 1, arr, visited, q)
    dfs(x, y + 1, arr, visited, q)


def shortestBridge(arr, n, m):

    # Declare a 2D visited array to keep track of the visited elements in dfs function.
    visited = [[False for i in range(m)] for j in range(n)]
    depths = [[0 for i in range(m)] for j in range(n)]
    q = deque()
    
    found = 0;

    # Run two nested loops to find first island.
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1:
                # Run a dfs to change all elements of this island to 2
                # And push all elements of this island to queue.
                dfs(i, j, arr, visited, q);
                found = 1;
                break;
        if (found):
            break
    
    '''
         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).
    '''
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
   
    while (len(q) > 0):
        frontNode = q.popleft()
        x = frontNode[0]
        y = frontNode[1];
        
        for i in range(4):
            newX = x + dx[i]
            newY = y + dy[i]
            
            if newX >= 0 and newX < n and newY >= 0 and newY < m:

                if visited[newX][newY] == False:
                    '''
                        If neighbour of (x,y) equals 1
                        Then we have found the second island.
                        Now, Return the length of shortest bridge.
                    '''
                    if arr[newX][newY] == 1:
                        return depths[x][y]
                    
                    # Push new neighbour of (x,y) for next iteration.
                    q.append((newX, newY))
                    visited[newX][newY] = True
                    # Assign depth of neighbour node as depth of (x,y) + 1.
                    depths[newX][newY] = depths[x][y] + 1;

/*
    Time Complexity  : O(N * M)
    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.
*/

#include 

// Dfs function to assign 2 to all elements of island 1.
void dfs(int x, int y, vector < vector < int >> & arr, vector < vector < bool >> & visited, queue < pair < int, int >> & q) {
    int rowSize = visited.size(), columnSize = visited[0].size();

    if (x < 0 or x >= rowSize or y < 0 or y >= columnSize) {
        return;
    }

    if (visited[x][y] == true) {
        return;
    }

    if (arr[x][y] != 1) {
        return;
    }

    visited[x][y] = true;
    arr[x][y] = 2;

    // Add (x,y) to queue to use it in BFS.
    q.push({ x, y});

    /*
        To check all the neighbours, recursively call in all 4 - directions of
        (x, y) i.e. (x – 1, y) , (x + 1, y) , (x, y–1) , (x, y + 1).
    */
    dfs(x - 1, y, arr, visited, q);
    dfs(x + 1, y, arr, visited, q);
    dfs(x, y - 1, arr, visited, q);
    dfs(x, y + 1, arr, visited, q);
}

int shortestBridge(vector < vector < int >> & arr, int n, int m) {
    vector < vector < bool >> visited(n, vector < bool > (m, false));

    vector < vector < int >> depth(n, vector < int > (m, 0));

    queue < pair < int, int >> q;

    bool found = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {

            // If arr[i][j] = 1 means we have founded a island.
            if (arr[i][j] == 1) {

                /*
                    Run a dfs to change all elements of this island to 2
                    And push all elements of this island to queue.
                */
                dfs(i, j, arr, visited, q);

                found = 1;
                break;
            }

        }
        
        if (found) {
            break;
        }

    }

    /*
         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).
    */
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    while (!q.empty()) {
        pair < int, int > frontNode = q.front();
        q.pop();

        int x = frontNode.first, y = frontNode.second;

        for (int i = 0; i < 4; i++) {
            int newX = frontNode.first + dx[i], newY = frontNode.second + dy[i];

            if (newX >= 0 and newX < n and newY >= 0 and newY < m) {
                if (!visited[newX][newY]) {
                    /*
                        If neighbour of (x,y) equals 1
                        Then we have found the second island
                        Now, Return the length of shortest bridge.
                    */
                    if (arr[newX][newY] == 1) {
                        return depth[x][y];
                    }

                    // Push new neighbour of (x,y) for next iteration.
                    q.push({ newX, newY });

                    visited[newX][newY] = true;

                    // Assign depth of neighbour node as depth of (x,y) + 1.
                    depth[newX][newY] = depth[x][y] + 1;
                }
            }
        }
    }
}

/*
    Time Complexity  : O(N * M)
    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.
*/

import java.util.Queue;
import java.util.LinkedList;
import javafx.util.Pair;
import java.util.ArrayList;

public class Solution {

    public static void dfs(int x, int y, ArrayList> arr, boolean[][] visited, Queue> q) {
        int rowSize = visited.length, columnSize = visited[0].length;

        if (x < 0 || x >= rowSize || y < 0 || y >= columnSize) {
            return;
        }

        if (visited[x][y] == true) {
            return;
        }

        if (arr.get(x).get(y) != 1) {
            return;
        }

        visited[x][y] = true;
        ArrayList updatedArrayList = arr.get(x);
        updatedArrayList.set(y,2);
        arr.set(x,updatedArrayList);

        q.add(new Pair(x,y));

        // To check all the neighbours, recursively call in all 4 - directions.  
        dfs(x - 1, y, arr, visited, q);
        dfs(x + 1, y, arr, visited, q);
        dfs(x, y - 1, arr, visited, q);
        dfs(x, y + 1, arr, visited, q);
    }

    public static int shortestBridge(ArrayList> arr, int n, int m) {
        boolean[][] visited = new boolean[n][m];
        for(int i=0;i            for(int j=0;j                visited[i][j] = false;
            }
        }

        int[][] depth = new int[n][m];

        Queue> q = new LinkedList<>();
        
        boolean found = false;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                // If arr[i][j] = 1 means we have founded a island.
                if (arr.get(i).get(j) == 1) {

                    /*
                        Run a dfs to change all elements of this island to 2
                        And push all elements of this island to queue.
                    */
                    dfs(i, j, arr, visited, q);

                    found = true;
                    break;
                }

            }

            if (found) {
                break;
            }
        }

        // Declare a direction array to visit neighbours of (x,y) in all four directions.
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        while (q.size() > 0) {
            Pair < Integer, Integer > frontNode = q.remove();

            int x = frontNode.getKey(), y = frontNode.getValue();

            for (int i = 0; i < 4; i++) {
                int newX = frontNode.getKey() + dx[i], newY = frontNode.getValue() + dy[i];

                if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
                    if (!visited[newX][newY]) {
                        /*
                            If neighbour of (x,y) equals 1
                            Then we have found the second island
                            Now, Return the length of shortest bridge.
                        */
                        if (arr.get(newX).get(newY) == 1) {
                            return depth[x][y];
                        }

                        // Push new neighbour of (x,y) for next iteration.
                        q.add(new Pair(newX,newY));

                        visited[newX][newY] = true;

                        // Assign depth of neighbour node as depth of (x,y) + 1.
                        depth[newX][newY] = depth[x][y] + 1;
                    }
                }
            }
        }
        
        return 0;
    }
}