题面

有一个城镇被划分为H行和W列的单元格网格。
如果 $S_i,_j$ 是' . '，则为道路；如果 $S_i,_j$ 为' # '，则为障碍物。

高桥将从家里去鱼市。他的房子在左上角的方格，鱼市在右下角的方格。

高桥可以从一个单元格向上、向下、向左或向右移动到可通过的单元格。他不能离开小镇，也不能进入街区。
但是，他可以一次摧毁一个 2$\times$2 正方形区域中的所有障碍物，使这个区域可以通过。

找到高桥进入鱼市所需的最少次数。

数据范围

• 2 $\le H,W \le 500$
• $H,W$ 是整数
• $S_i,_j$ 只会是 ' . ' 或 ' # '
• $S_1,_1$ 和 $S_H,_W$ 都是 ' . '

样例解释

1. 通过打破 $S_3,_2 S_3,_3 S_4,_2 S_4,_3$ 这个2$\times$2 的正方形区域，高桥可以顺利到达鱼市。
2. 高桥不需要打破障碍物就可以顺利到达鱼市，尽管他需要绕路。