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

答えを出力せよ。

Sample Explanation 1

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

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

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

Sample Explanation 2

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