分数: 500 点
问题陈述
有一个网格 H 行和 W 列。我们将参考位于 i从顶部开始的第行和 j从左侧算起的第 列作为单元格 (i,j)。每个单元格上最多放置一面镜子。
高桥站在牢房的左侧 (1,1),青木站在牢房的右侧 (H,W)。高桥拿着手电筒,从牢房的左侧照射光 (1,1) 向右。这里,假设手电筒的光没有漫射,并且是直线传播的光线。
高桥的目标是利用网格中的镜子将手电筒的光传递给青木。
镜子放置方式分为三种类型。当光线照射到镜子时,光线的方向会根据镜子的位置而改变。对于每个镜子的放置,每个进入方向的退出方向如下图所示。
- A型(未放置镜子)

- B型(镜子放置在连接左上和右下的对角线上)

- C型(镜子放置在连接右上和左下的对角线上)

网格上的镜子位置由下式表示 H 长度的字符串 W: S_1,S_2,\ldots,S_H。当 j- 第一个字符 S_i is A,细胞 (i,j) 是 A 型;当它是 B,细胞 (i,j) 是 B 型;当它是 C,细胞 (i,j) 是 C 型。
高桥可以执行任意多次以下操作,将光传递给青木:
- 选择一个单元格并将该单元格的镜像位置更改为其他类型。
求将光传递给 Aoki 所需的最少操作次数。
你被给予 T 测试用例;找到每个问题的答案。
约束
- 1\leq T
- 1\leq H,W
- HW\leq 2\times 10^5
- S_i 是一个长度为 W 组成
A,B,C. - T, H,和 W 是整数。
- 总和 HW 所有测试用例最多 2\times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
H W S_1 S_2 \vdots S_H
输出
输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
4 3 4 ABCB CACC BCBA 2 2 CB AA 1 10 BCBCBCBCBC 10 10 CCAABACAAA CCCBACACCA BACAABCBBA ACCCAACCCA CCAAAACCBA AACBBACCAA BCCCACBBAB CBBCAACCCC CBBCCBCBCA BBACABBACC
示例输出 1
0 2 10 5
对于第一个测试用例,无需执行任何操作即可将光传递给 Aoki。

对于第二个测试用例,通过更改单元格的镜像位置 (1,1) A 型和单元格的镜像放置 (2,2) 对于B型,光线可以传递到Aoki,如下图所示。不可能通过一次或更少的操作将光传递给青木,所以答案是 2.
