Minimum Number of Bridges

Given a grid representing a city's map where each cell is either land (0) or water (1), determine the minimum number of bridges required to create a path from the leftmost column to the rightmost column. Bridges can be built only on water cells. Movement is allowed in eight directions, i.e., horizontally, vertically, and diagonally. If no such path exists, output -1.

The journey starts only from a cell in the leftmost column that is land (0). While moving to water cells, each water cell stepped into adds 1 to your bridge count. Your task is to compute the minimum total number of bridges built to achieve the crossing.

Note: Any formula present is expressed in \(\LaTeX\) format.

inputFormat

The first line of input contains two integers \(m\) and \(n\) representing the number of rows and columns respectively. The following \(m\) lines each contain \(n\) integers (0 or 1) separated by spaces representing the city map.

outputFormat

Output a single integer that represents the minimum number of bridges required to connect the leftmost column to the rightmost column. If it is not possible to set up such a connection, output -1.

## sample

4 5
0 1 0 0 0
0 1 1 1 0
0 0 0 1 0
1 1 0 0 0

1

</p>