/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : {500} 点
問題文
H 行 W 列のマス目があります。 上から i 行目、左から j 列目のマスをマス (i,j) と呼ぶことにします。各マスには鏡が高々 1 枚置いてあります。
高橋君はマス (1,1) の左側、青木くんはマス (H,W) の右側に立っています。高橋君は懐中電灯を持っており、マス (1,1) の左側から右に向かって光を入れています。ここで、懐中電灯の光は拡散せず、まっすぐに進む光線であるとします。
高橋君の目標は、マス目にある鏡を利用して懐中電灯の光を青木君に届けることです。
鏡の置き方は次の 3 種類あります。光が鏡に当たると、鏡の置き方に応じて光の進む向きが変わります。それぞれの鏡の置き方について、光が入る方向に対する出る方向は下図のようになります。
- タイプ A （鏡は置かれていない）
- タイプ B （左上と右下を結ぶ対角線上に鏡が置かれている）
- タイプ C （右上と左下を結ぶ対角線上に鏡が置かれている）
マス目の鏡の置き方は H 個の長さ W の文字列 S_1,S_2,\ldots,S_H で表されます。S_i の j 文字目が A のときマス (i,j) はタイプ A、B のときマス (i,j) はタイプ B、C のときマス (i,j) はタイプ C です。
高橋君は、青木君に光を届けるために以下の操作を好きな回数行うことができます。
- あるマスを 1 つ選び、そのマスの鏡の置き方を別のタイプに変更する
青木君に光を届けるためには最低何回操作を行う必要があるか求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 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 以下
入力
入力は以下の形式で標準入力から与えられる。
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
1 つ目のテストケースについて、操作を行わなくても青木君に光を届けることができます。
2 つ目のテストケースについて、マス (1,1) の鏡の置き方をタイプ A に、マス (2,2) の鏡の置き方をタイプ B に変更することで、下図のように青木君に光を届けることができます。1 回以下の操作で青木君に光を届けることはできないので、答えは 2 です。
Score : 500 points
Problem Statement
There is a grid with H rows and W columns. We will refer to the cell at the i-th row from the top and j-th column from the left as cell (i,j). Each cell has at most one mirror placed on it.
Takahashi is standing on the left side of cell (1,1), and Aoki is standing on the right side of cell (H,W). Takahashi has a flashlight and is shining light from the left side of cell (1,1) toward the right. Here, assume that the flashlight's light does not diffuse and is a light ray that travels straight.
Takahashi's goal is to deliver the flashlight's light to Aoki by using the mirrors in the grid.
There are three types of mirror placements. When light hits a mirror, the direction of the light changes according to the mirror placement. For each mirror placement, the exit direction for each entry direction is as shown in the figures below.
- Type A (no mirror is placed)
- Type B (a mirror is placed on the diagonal connecting the upper-left and lower-right)
- Type C (a mirror is placed on the diagonal connecting the upper-right and lower-left)
The mirror placement on the grid is represented by H strings of length W: S_1,S_2,\ldots,S_H. When the j-th character of S_i is A, cell (i,j) is type A; when it is B, cell (i,j) is type B; when it is C, cell (i,j) is type C.
Takahashi can perform the following operation any number of times to deliver the light to Aoki:
- Choose one cell and change the mirror placement of that cell to a different type.
Find the minimum number of operations needed to deliver the light to Aoki.
You are given T test cases; find the answer for each.
Constraints
- 1\leq T
- 1\leq H,W
- HW\leq 2\times 10^5
- S_i is a string of length W consisting of
A,B,C. - T, H, and W are integers.
- The sum of HW over all test cases is at most 2\times 10^5.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
H W S_1 S_2 \vdots S_H
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 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
Sample Output 1
0 2 10 5
For the first test case, the light can be delivered to Aoki without performing any operations.
For the second test case, by changing the mirror placement of cell (1,1) to type A and the mirror placement of cell (2,2) to type B, the light can be delivered to Aoki as shown in the figure below. It is impossible to deliver the light to Aoki with one or fewer operations, so the answer is 2.