P2130 The Sprinting Wzf

As everyone knows, Wzf always wants to do homework. But today, WSD snatched its homework!!! Wzf is furious!!! It decides to rush toward the homework at top speed. In front of it is a maze, and the homework is inside!

There is a maze with $n$ rows and $m$ columns: |标识|含义| |:-:|:-:| |`$`|Empty cell, walkable.| |`.`|Also an empty cell, also walkable.| |`X`|Obstacle, not walkable.| |`#`|Goal; Wzf's homework is here.| Wzf starts from the top-left corner of the maze (row $1$, column $1$). Each second, it can: 1. Choose a direction (up / down / left / right). 2. Choose a non-negative integer $m$. 3. Take one step in the chosen direction, moving $2^m$ cells: - It must not cross any obstacle along the way. - The landing cell must not contain an obstacle. - It cannot go outside the maze. Find the minimum number of seconds Wzf needs to reach the goal.

The first line contains two integers $n, m$ with $1 \le n, m \le 1000$. The next $n$ lines each contain $m$ characters. It is guaranteed that there is exactly one `#`. It is guaranteed that the cell at row $\bm 1$, column $\bm 1$ is not `X`.

Output a single integer, the minimum number of seconds Wzf needs to reach the goal. If Wzf cannot reach the goal, output $-1$.

Translated by ChatGPT 5