AT_abc431_e.[ABC431E] Reflection on Grid

给定一个有 $H$ 行 $W$ 列的网格。我们将第 $i$ 行第 $j$ 列的格子称为 $(i, j)$。每个格子上至多放有一面镜子。

高桥站在 $(1,1)$ 格子的左侧，青木站在 $(H,W)$ 格子的右侧。高桥手持手电筒，从 $(1,1)$ 格子的左侧向右照射光线。这里认为手电筒的光不会发散，是一条直线光。

高桥的目标是通过利用网格中的镜子将手电筒的光传递给青木。

镜子的放置有三种类型。当光线照射到镜子时，光线会根据镜子的类型改变方向。每种镜子，对于不同的入射方向，其出射方向如下图所示。

• A型（未放置镜子）

• B型（镜子放置在左上与右下的对角线上）

• C型（镜子放置在右上与左下的对角线上）

网格上的镜子放置情况由 $H$ 个长度为 $W$ 的字符串 $S_1,S_2,\ldots,S_H$ 给出。当 $S_i$ 的第 $j$ 个字符为 A 时，表示 $(i,j)$ 格子为A型；为 B 时为B型；为 C 时为C型。

高桥可以进行如下操作任意次以将光线传递给青木：

• 选择一个格子，并将该格子的镜子类型更换为不同的类型。

请你求出将光线传递给青木至少需要多少次操作。

共有 $T$ 组测试数据，请分别求解每组的答案。

输入由标准输入给出，格式如下：

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

每组测试数据格式如下：

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

样例解释 1

对于第一组数据，不需要进行任何操作即可将光线传递给青木。

对于第二组数据，通过将 $(1,1)$ 处的镜子类型更换为A型、$(2,2)$ 处的镜子类型更换为B型，可以如图所示地将光线传递给青木。无法通过一步或更少的操作实现目标，因此答案为 $2$。

数据范围

• $1\leq T$
• $1\leq H,W$
• $HW\leq 2\times 10^5$
• $S_i$ 为仅由A、B、C组成的长度为 $W$ 的字符串。
• $T$、 $H$ 、$W$ 均为整数。
• 所有测试数据中 $HW$ 之和不超过 $2\times 10^5$。

由 ChatGPT 5 翻译