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 翻译