Slime Escape
本题没有可用的提交语言。
Description
Nikita received a slime-making kit as a birthday gift. Excited about the present, Nikita created a square-shaped slime and placed it on the table. However, the slime got scared of Nikita's upcoming experiments and decided to escape.
The table is represented as a rectangular field with $n$ rows and $m$ columns. Some cells on the table contain holes, and if any of the slime's cells end up on a hole, it will fall off the table. The slime occupies 4 cells and initially starts in the top-left with size $2 \times 2$. Its goal is to reach the bottom-right corner of size $2 \times 2$.
The slime can move across the table using transformations. A transformation involves moving one of the slime's cells to another cell adjacent to it, sharing either a side or a corner. After each transformation, the slime must form a 4-connected shape (in other words, there must be a path between any two slime cells, with each step being adjacent to the previous cell by a side).
The slime wants to escape from Nikita as quickly as possible, ensuring that its cells never end up on any holes. Find the minimum number of transformations it needs to achieve this.
The first line contains two integers $n$ and $m$ ($2 \le n, m \le 3 \cdot 10^5$; $n \cdot m \le 3 \cdot 10^5$) — the dimensions of the table.
The next $n$ lines contain $m$ characters $a_{i, j}$, describing the table. The character "#" represents a hole in the table, and the character "." represents the table's surface.
It is guaranteed that the top-left and bottom-right corners of size $2 \times 2$ are part of the table's surface.
Output the minimum number of transformations required for the slime to occupy the bottom-right corner of size $2 \times 2$, starting from the top-left corner. If it is not possible, output $-1$.
Input
The first line contains two integers $n$ and $m$ ($2 \le n, m \le 3 \cdot 10^5$; $n \cdot m \le 3 \cdot 10^5$) — the dimensions of the table.
The next $n$ lines contain $m$ characters $a_{i, j}$, describing the table. The character "#" represents a hole in the table, and the character "." represents the table's surface.
It is guaranteed that the top-left and bottom-right corners of size $2 \times 2$ are part of the table's surface.
Output
Output the minimum number of transformations required for the slime to occupy the bottom-right corner of size $2 \times 2$, starting from the top-left corner. If it is not possible, output $-1$.
3 3
..#
...
#..
3 5
..###
.....
##...
5
-1
Note
The figure below shows the transformations for the first example. The black cells represent holes in the table, and the gray cells represent the slime. The arrows indicate the movement of cells.
