题目描述

给定一个$n×m$的迷宫，其中每个格子为.（空地）或#（障碍）。玩家从左上角$(1, 1)$出发，目标是到达右下角$(n, m)$ 。每步可以向上、下、左、右移动一格，但不能移动到迷宫外部或障碍格子上。玩家可以选择至多一次服用一种药剂，在服药后的连续$k(k≥0)$步中，可以将障碍视为可以通行的空地，需要计算从起点到终点可达的前提下，所需的最小$k$值。

输入格式

第一行两个正整数$n,m$ ($2 \le n,m \le 1000$)，表示迷宫的大小。 接下来一个$n×m$的矩阵，表示迷宫。保证起点和终点不为障碍。

输出格式

输出一行，表示$k$的最小值。

样例1

输入

3 4
..##
###.
.##.

输出

2

样例2

输入

3 2
..
##
..

输出

1

样例解释

对于样例一，一种最优的路线为：$(1,1)→(1,2)→(1,3)→(1,4)→(2,4)→(3,4)$，在到达$(1, 2)$时服用药剂，将随后的$(1, 3)$和$(1, 4)$视为空地。

对于样例二，一种最优的路线为：$(1,1)→(1,2)→(2,2)→(3,2)$ ，在到达$(1, 2)$时服用药剂，将随后的$(2, 2)$视为空地。

数据分布

对于 $40\%$ 的样例，保证 $1 \le n,m \le 10$

对于 $100\%$ 的样例，保证 $1 \le n,m \le 1000$

时空限制

• 时间限制：$1s$
• 空间限制：$256M$