99991323 - [ABC213E] Stronger Takahashi

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

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

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

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

输入

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

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} .

输出

答えを出力せよ。

样例

输入

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

输出

1

输入

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

输出

0

输入

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

输出

5

提示

Sample Explanation 1

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

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

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

Sample Explanation 2

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

时间限制 4 秒
内存限制 128 MB
讨论 统计
上一题 下一题