Shortest Bridge Problem Statement

Two characters, Tony Stark and Thanos, reside on two separate islands within a 2-D binary matrix of dimensions N x M. Each matrix cell has a value of either 1 (land) or 0 (water). The two islands are distinct connected components of 1s, connected either vertically or horizontally. Your task is to help Tony construct a bridge by converting some 0s to 1s, thereby connecting the two islands with the minimum number of 0 to 1 conversions.

Explanation:

Your objective is to find the shortest path of transformed 0s that connects the two islands.

Input:

The input starts with an integer 'T', indicating the number of test cases.
For each test case:
The first line consists of two integers N and M, denoting the number of rows and columns, respectively, of the 2-D array.
The subsequent N lines each contain M space-separated integers (either 0 or 1) representing the elements of the matrix.

Output:

Output the minimal length of the bridge needed to connect the two islands for each test case on separate lines.

Example:

Example Input:
T = 1
N = 3, M = 3
Matrix:
1 1 0
0 1 0
0 0 1

Example Output:
1

Explanation:

The bridge with the minimal number of 0s to convert to 1 connects the two islands with only one conversion.

Constraints:

• 1 <= T <= 5
• 1 <= N, M <= 100
• 0 <= ARR[i][j] <= 1
• Each ARR[i][j] is either a 0 (water) or a 1 (land).
• Time Limit: 1 second

Note:

You do not need to handle input or output directly. Your task is to implement the function to solve the problem.