小红的皇后

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

题目描述

有一个 $n$ 行 $m$ 列的棋盘，有一些格子是障碍物不能通过。小红控制一个皇后在从左上角出发，每次移动她可以控制皇后进行以下三种方式中的一种：
1. 向右移动若干个格子。
2. 向下移动若干个格子。
3，向右下移动若干个格子。
用数学语言描述，当前的坐标在 $(x,y)$ 时，每次移动可以到 $(x+k,y)$ 或 $(x,y+k)$ 或 $(x+k,y+k)$ ，其中 $k$ 为任意正整数。移动的前提是，路径上没有障碍物。
小红想知道，皇后从左上角移动到右下角，最少要移动多少步？

输入描述:

第一行输入两个正整数和，代表行数和列数。
接下来的行，每行输入一个长度的字符串，用来表示棋盘。
其中'.'代表可以通过的位置，'*'代表障碍物。
保证左上角和右下角都不是障碍物。

输出描述:

如果无法到达，请输出-1。
否则输出一个整数，代表最少的移动次数。

示例1

输入

复制

3 3
...
.**
.*.

输出

复制

-1

示例2

输入

复制

3 4
....
**.*
....

输出

复制