Move by Breaking One Wall

You are given a map represented by an N × M grid. In the grid, 0 means a cell you can move through, and 1 means a wall.

Starting from (1, 1), find the shortest path to (N, M). The length of a path is the number of cells it visits, including both the starting cell and the destination cell.

If breaking one wall can make the route possible or shorter, you may break at most one wall while moving.

From any cell, you may move to one of the four adjacent cells: up, down, left, or right.

Given the map, write a program that outputs the length of the shortest possible path.

The first line contains N and M (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 1,000).

Each of the next N lines contains M digits describing the map.

The cells (1, 1) and (N, M) are always 0.

Print the length of the shortest path. If reaching the destination is impossible, print -1.