← 返回题目列表

AtCoder · abc431_e

H. 网格反思

中文机器翻译题面 查看原题

分数: 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.