小红的大蘑菇（hard）

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

题目描述

$\hspace{15pt}$ 本题与《小红的大蘑菇（easy）》共享题目背景，但是所求内容不同，我们建议您重新阅读题面。

$\hspace{15pt}$ 在一个 $n$ 行 $m$ 列的网格里有一些蘑菇，我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。每个方格要么是空地（使用字符 $\texttt{`.'}$ 表示），要么是小蘑菇（使用字符 $\texttt{`*'}$ 表示），要么是大蘑菇（使用字符 $\texttt{`\#'}$ 表示）。
$\hspace{15pt}$ 如果一个坐标到全部小蘑菇的曼哈顿距离均大于 $1$ ，且到全部大蘑菇的曼哈顿距离均大于 $2$ ，那么这个坐标就是安全的。
$\hspace{15pt}$ 你可以沿着空方格上下左右随意移动：从 $(x,y)$ 向上移动一格即抵达 $(x-1,y)$ 、向下移动一格即抵达 $(x+1,y)$ 、向左移动一格即抵达 $(x,y-1)$ 、向右移动一格即抵达 $(x,y+1)$ 。特别的，你不能走出地图的边界。小红想知道，在只走安全的空地的前提下，从左上角 $(1,1)$ 走到右下角 $(n,m)$ 需要最少走多少步？如果无法到达右下角，直接输出 $-1$ 。

$\hspace{15pt}$ 我们定义， $(x_1,y_1)$ 到 $(x_2,y_2)$ 的曼哈顿距离为 $|x_1-x_2|+|y_1-y_2|$ 。

输入描述:

第一行输入两个正整数  代表地图的行数、列数。 
此后  行，第  行输入一个长度为  的字符串 ，用来表示地图。其中， 代表  为空地， 代表小蘑菇， 代表大蘑菇。

输出描述:

如果无法到达右下角、或起点与终点不安全，直接输出 。
否则，输出一个整数，代表需要的最少步数。

示例1

输入

复制

3 8
..*.....
........
.....*..

输出

复制

说明

行走方式如下图，最少需要走13步：

示例2

输入

复制

1 1
.

输出

复制

示例3

输入

复制

3 3
#..
...
...

输出

复制

-1