题目描述

一天 33DAI 在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 $n\times m$ 的格点组成，每个格点只有2种状态，. 和 #，前者表示道路，后者表示围墙。

33DAI 现在在左上角，他希望走到右下角的位置，他有两种移动方式：

• 如果当前位置是道路，那么可以走到上下左右相邻的道路中。
• 不管当前位置是什么，都可以跳跃到上下左右四个方向间隔一个格点的位置（不管那个位置是道路还是围墙）。
  • 即可以从 $(x,y)$ 跳跃到 $(x+2,y),(x-2,y),(x,y+2),(x,y-2)$ 四个位置之一（当然前提条件是这四个位置都在地图内）。

请问 33DAI 最少使用几次跳跃可以从左上角走到右下角。如果无论如何都无法到达，输出 -1。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行由 $m$ 个字符构成。即 $n\times m$ 的格点。

输出格式

一个数，即最少跳跃次数。

4 7
.######
.#.....
##.####
...#...

2

1 9
#########

4

1 10
##########

-1

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,m \le 1000$。

• 子任务 1（30 分）：保证所有位置都是围墙。
• 子任务 2（30 分）：保证 $n = 1$。
• 子任务 3（40 分）：没有特殊限制。