AT_abc213_e [ABC213E] Stronger Takahashi

有一座城市被划分为 $H$ 行 $W$ 列的格子状区块。从上往下第 $i$ 行，从左往右第 $j$ 列的区块，若 $S_{i,j}$ 为 `.`，则表示道路；若为 `#`，则表示围墙。 高桥君打算从自己家出发去鱼店买东西。高桥君的家在城市的左上角区块，鱼店在城市的右下角区块。 高桥君可以从当前所在的区块移动到上下左右相邻的道路区块。不能走出城市外部，也不能移动到围墙区块。不过，高桥君力大无穷，可以每次用一拳将任意 $2\times 2$ 的区块内的围墙全部打碎变成道路。 请你求出高桥君到达鱼店至少需要出拳多少次。

输入以以下格式从标准输入给出。 > $H$ $W$ > $S_{1,1} \ldots S_{1,W}$ > $\vdots$ > $S_{H,1} \ldots S_{H,W}$

请输出答案。

### 限制条件 - $2 \leq H, W \leq 500$ - $H, W$ 为整数 - $S_{i,j}$ 仅为 `.` 或 `#` - $S_{1,1}$ 和 $S_{H,W}$ 均为 `.` ### 样例解释 1 例如，如果破坏用 `*` 表示的 $2\times 2$ 区块内的围墙，就能到达鱼店。 ``` ..#.. #.**# ##**# #.#.# ..#.. ``` 被破坏的 $2\times 2$ 区块不要求全部为围墙。 ### 样例解释 2 虽然需要绕远路，但无需破坏任何围墙也能到达鱼店。 由 ChatGPT 4.1 翻译