/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
H 行 W 列の格子状の区画に区切られた街があります。上から i 行目、左から j 列目の区画は、S_{i,j} が . のとき道、# のとき塀です。
高橋君は自分の家から魚屋に買い物に行くことにしました。高橋君の家は街の左上隅の区画にあり、魚屋は街の右下隅の区画にあります。
高橋君は、自分がいる区画から上下左右に隣接する道の区画に移動することができます。街の外に出ることはできません。
塀の区画に移動することはできませんが、高橋君は非常に腕力が強いため、パンチを 1 回繰り出すことで任意の 2\times 2 の区画内の塀を壊して道にすることができます。
高橋君が魚屋にたどり着くためには、最低何回パンチを繰り出せばよいか求めてください。
制約
- 2 \leq H,W \leq 500
- H,W は整数
- S_{i,j} は
.または# - S_{1,1} と S_{H,W} は
.
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1} \ldots S_{1,W}
\vdots
S_{H,1} \ldots S_{H,W}
出力
答えを出力せよ。
入力例 1
5 5 ..#.. #.#.# ##.## #.#.# ..#..
出力例 1
1
例えば、以下の * で表す 2\times 2 の区画にある塀を破壊すると魚屋にたどり着くことができます。
..#.. #.**# ##**# #.#.# ..#..
破壊対象の 2 \times 2 の区画の全てが塀である必要はありません。
入力例 2
5 7 ....... ######. ....... .###### .......
出力例 2
0
遠回りが必要ですが、塀を破壊することなく魚屋にたどり着くことができます。
入力例 3
8 8 .####### ######## ######## ######## ######## ######## ######## #######.
出力例 3
5
Score : 500 points
Problem Statement
There is a town divided into a grid of cells with H rows and W columns. The cell at the i-th row from the top and j-th column from the left is a passable space if S_{i,j} is . and a block if S_{i,j} is #.
Takahashi will go from his house to a fish market. His house is in the cell at the top-left corner, and the fish market is in the cell at the bottom-right corner.
Takahashi can move one cell up, down, left, or right to a passable cell. He cannot leave the town. He cannot enter a block, either. However, his physical strength allows him to destroy all blocks in a square region with 2\times 2 cells of his choice with one punch, making these cells passable.
Find the minimum number of punches needed for Takahashi to reach the fish market.
Constraints
- 2 \leq H,W \leq 500
- H and W are integers.
- S_{i,j} is
.or#. - S_{1,1} and S_{H,W} are
..
Input
Input is given from Standard Input in the following format:
H W
S_{1,1} \ldots S_{1,W}
\vdots
S_{H,1} \ldots S_{H,W}
Output
Print the answer.
Sample Input 1
5 5 ..#.. #.#.# ##.## #.#.# ..#..
Sample Output 1
1
He can reach the fish market by, for example, destroying the blocks in the square region with 2\times 2 cells marked * below.
..#.. #.**# ##**# #.#.# ..#..
It is not required that all of the 2\times 2 cells in the region to punch are blocks.
Sample Input 2
5 7 ....... ######. ....... .###### .......
Sample Output 2
0
He can reach the fish market without destroying blocks, though he has to go a long way around.
Sample Input 3
8 8 .####### ######## ######## ######## ######## ######## ######## #######.
Sample Output 3
5