99991323 - [ABC213E] Stronger Takahashi

通过次数

8

提交次数

24

Time Limit : 4 秒
Memory Limit : 128 MB

有一个城市,被分成了 H W 列的格子状的区域。如果第 i 行,第 j 列的区域 S_{i,j} .,那么就是道路,如果是 #,那么就是墙。

高桥君想从自己的家去鱼店买东西。高桥君的家在城市的左上角的区域,鱼店在城市的右下角的区域。

高桥君可以从自己所在的区域移动到上下左右相邻的道路区域。他不能离开城市。 他不能移动到墙的区域,但是高桥君非常有力量,所以他可以用一次拳头打碎任意一个 2\times\ 2 的区域内的墙,把它们变成道路。

请问高桥君要到达鱼店,至少要打碎多少次墙?

Input

输入按以下格式从标准输入给出。

H W
S_{1,1} ... S_{1,W}
:
S_{H,1} ... S_{H,W}
  • 2\ \leq\ H,W\ \leq\ 500
  • H,W 是整数
  • S_{i,j} . 或者 #
  • S_{1,1} .
  • S_{H,W} .

Output

答えを出力せよ。

Examples

Input

5 5
..#..
#.#.#
##.##
#.#.#
..#..

Output

1

Input

5 7
.......
######.
.......
.######
.......

Output

0

Input

8 8
.#######
########
########
########
########
########
########
#######.

Output

5

Hint

Sample Explanation 1

例えば、以下の * で表す 2\times\ 2 の区画にある塀を破壊すると魚屋にたどり着くことができます。 `

..#..
#.**#
##**#
#.#.#
..#..

破壊対象の 2\ \times\ 2 の区画の全てが塀である必要はありません。

Sample Explanation 2

遠回りが必要ですが、塀を破壊することなく魚屋にたどり着くことができます。