题目描述

给定一个大小为 $W\times H$ 的规则方格，其中一些单位方格被封锁。你需要从点 $(0,0)$ 出发，到达点 $(W,H)$，并且路径不能穿过任何被封锁方格的内部。

路径只能由若干段 $90^\circ$ 圆弧（四分之一圆）组成。每段圆弧必须满足：

• 半径为正整数，因此圆弧的起点和终点都位于整数格点上；
• 圆弧在起点和终点处的切线都必须与 $x$ 轴或 $y$ 轴平行；
• 圆弧不能穿过任何被封锁方格的内部。

圆弧允许经过被封锁方格的角点，也允许从两个仅共享一个角点的封锁方格之间穿过。路径本身允许自交。

网格中 . 表示空方格，# 表示被封锁方格。

请找出从 $(0,0)$ 到 $(W,H)$ 所需圆弧数量的最小值。如果不存在合法路径，输出 $-1$。

下图给出了一个圆弧路径示意：

输入格式

第一行输入两个整数 $H,W$，分别表示网格的行数和列数。

接下来 $H$ 行，每行一个长度为 $W$ 的字符串，只包含字符 . 和 #。

第 $i$ 行第 $j$ 个字符描述对应的单位方格是否被封锁。

输出格式

输出一个整数，表示从 $(0,0)$ 到 $(W,H)$ 所需的最少圆弧数。

若不存在合法路径，输出 $-1$。

样例 1

输入

2 2
..
..

输出

1

样例 2

输入

2 3
...
...

输出

-1

样例 3

输入

6 4
....
.##.
.##.
.##.
.##.
....

输出

7

样例 4

输入

8 12
....########
###..###...#
..##..#.##.#
...##..#...#
....#..#...#
....#..###..
....####.##.
..........#.

输出

4

样例解释

• 样例 1 中，只需一个半径为 $2$ 的四分之一圆即可从 $(0,0)$ 到达 $(2,2)$。
• 样例 2 的两个维度奇偶性不同，因此无法由若干四分之一圆连接两个对角点。
• 样例 3 中至少需要 $7$ 段半径为 $1$ 的圆弧。
• 样例 4 即题目示意中的情形，最优答案为 $4$。

数据范围

• $1\le H,W\le 50$；
• 网格中的每个字符均为 . 或 #。