AT_arc214_f [ARC214F] Unpredictable Moves

有一个 $H \times W$ 的网格。记 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。 每个格子是空地或墙，信息由 $H \times W$ 个字符 $S_{1,1},\dots ,S_{H,W}$ 表示。如果 $S_{i,j}$ 为 `.`，则 $(i,j)$ 是空地；如果为 `#`，则为墙。 起初，Takahashi 在 $(1,1)$ 格子。他每次可以向相邻的上下左右四个方向之一移动任意次数。但**他不能连续两次向同一个方向移动**。另外，他不能移动到墙格，也不能走出网格。 出发前，他可以破坏若干个墙格，使其变为空地。为了能够到达 $(H,W)$，他最少需要破坏多少个墙格？在本题约束下，可以证明必定存在某种破坏墙格的方法使他能到达 $(H,W)$。 共有 $T$ 组测试数据；请分别求解。

输入由标准输入给出，格式如下： > $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ 每组测试数据格式如下： > $H$ $W$ $S_{1,1}$ $S_{1,2}$ $\ldots$ $S_{1,W}$ > $S_{2,1}$ $S_{2,2}$ $\ldots$ $S_{2,W}$ > $\vdots$ > $S_{H,1}$ $S_{H,2}$ $\ldots$ $S_{H,W}$

输出 $T$ 行。 第 $i$ 行输出第 $i$ 组测试数据，为 Takahashi 能到达 $(H,W)$ 所需破坏的最少墙格数量。

### 样例解释 1 对于第一个测试点，Takahashi 可以通过破坏下图所示的两个墙格到达 $(H,W)$。  左边展示了需要破坏的墙格，右边给出了一个移动路径。注意，不要求移动次数最少，也可以多次经过同一个格子。 对于第二个测试点，无需破坏任何墙格即可到达 $(H,W)$。 ### 约束条件 - $1 \le T \le 1000$ - $2 \le H, W \le 100$ - $S_{i,j}$ 为 `.` 或 `#`。 - $S_{1,1}$ 和 $S_{H,W}$ 均为 `.`。 - 所有测试数据的 $HW$ 之和不超过 $3\times 10^4$。 由 ChatGPT 5 翻译