Shortest Bridge

You are given an m x n grid consisting of 0's (water) and 1's (land) where there are exactly two islands. An island is a group of adjacent 1's connected 4-directionally (up, down, left, right). Your task is to connect the two islands by flipping as few 0's to 1's as possible. The answer is the minimum number of 0's that need to be flipped.

In other words, if you consider the number of water cells flipped along the shortest path that connects any cell from one island to any cell of the other island, you need to find the minimum such number.

The connection length can be formulated as: \(steps = \min_{\text{path}}(\text{number of water cells flipped})\).

Note: It is guaranteed that there exists exactly two islands in the grid.

inputFormat

The first line contains two integers m and n -- the number of rows and columns of the grid.

The next m lines each contain n space-separated integers (either 0 or 1) representing the grid.

outputFormat

Output a single integer, the minimum number of 0's that need to be flipped to connect the two islands.

2 2
0 1
1 0

1