小红走矩阵
题号：NC276116
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\,\,\,\,\,\,\,\,\,\,n \times m 的矩阵由障碍和空地组成，初始时小红位于起点 (1, 1) ，她想要前往终点 (n,m) 。小红每一步可以往上下左右四个方向的空地移动一格。
\,\,\,\,\,\,\,\,\,\,小红在起点处可以进行最多一次操作：选择矩阵中的一处障碍替换为空地，但代价是小红必须选择失去向上下左右四个方向中一个移动的能力。
\,\,\,\,\,\,\,\,\,\,求小红从起点到达终点的最小步数，如果无法到达则输出 -1 。

输入描述:

\,\,\,\,\,\,\,\,\,\,第一行输入两个整数 n, m\ (1 \leq n, m \leq 1000) 代表矩阵的大小。
\,\,\,\,\,\,\,\,\,\,此后 n 行，每行输入 m 个字符 a_1a_2\dots a_n\ (a_i\in\{'\rm X','\rm .'\}) 描述矩阵中这一行的情况，其中 '\rm X'（Ascii：88）代表障碍，'\rm .'（Ascii：46）代表空地。保证起点和终点都是空地。

输出描述:

\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，表示小红从起点到达终点的最小步数；如果无论怎么操作都无法到达，则直接输出 -1 。
示例1

输入

复制 
4 4
..X.
XXX.
.X..
.X..

输出

复制 
6

说明

\,\,\,\,\,\,\,\,\,\,小红失去向上走的能力，消除 (1, 3) 处障碍，从起点到终点的最小步数为 6 。
示例2

输入

复制 
4 4
.XX.
XXX.
.X..
.X..

输出

复制 
-1

说明

\,\,\,\,\,\,\,\,\,\,小红最多只能删除一个障碍，无法到达终点。