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