この問題をグラフの問題に言い換えます．

グリッドの各辺について，その辺を通過する \(2\) つの向きそれぞれに対応する頂点を作ります．（下図）

それぞれの鏡の置き方について，上で作った頂点間に以下のような有向辺が張ってあると考えることができます．

このとき，あるマスの鏡を別の置き方に変更することは，各頂点の有向辺の行先を変えることとみなすことができます．すなわち，もともといける頂点には変更コスト \(0\) で，それ以外の頂点には変更コスト \(1\) で移動できるとみなすことができます．

（タイプ A の場合．赤線がコスト \(0\)，青線がコスト \(1\)）

このように言い換えることで，01-BFS で解ける形に帰着出来ました．

実装方法について，\(4\) 方向にそれぞれ番号を付けて，\(\mathrm{dp}[x][y][d]\) で「マス \((x, y)\) から方向 \(d\) に対応する頂点について，その頂点に到達するまでに必要な最小コスト」とするとよいでしょう．

以下の実装例では次のような工夫をしています．

• 下右上左の順に方向に番号をそれぞれ \(0, 1, 2, 3\) と名付ける．今いるマスを \((x, y)\) ，マス \((x, y)\) に入ってくるときの方向を \(\mathrm{dir}\)，マス \((x, y)\) から出ていく方向を \(\mathrm{ndir}\) としたとき，
  • \(\mathrm{dir}\oplus \mathrm{ndir}=2\) となるような移動はできない．
  • \(S[x][y]\) が A の場合：\(\mathrm{dir}\oplus \mathrm{ndir}=0\) ならばコスト \(0\) ，それ以外はコスト \(1\)
  • \(S[x][y]\) が B の場合：\(\mathrm{dir}\oplus \mathrm{ndir}=1\) ならばコスト \(0\) ，それ以外はコスト \(1\)
  • \(S[x][y]\) が C の場合：\(\mathrm{dir}\oplus \mathrm{ndir}=3\) ならばコスト \(0\) ，それ以外はコスト \(1\)

from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
d = {"A": 0, "B": 1, "C": 3}


def solve():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]
    dp = [[[1 << 30] * 4 for _ in range(w)] for _ in range(h)]

    dq = deque()
    dq.append((0, 0, -1, 1))
    while dq:
        c, pre_x, pre_y, dir = dq.popleft()
        x, y = pre_x + dx[dir], pre_y + dy[dir]
        if not (0 <= x < h and 0 <= y < w):
            continue
        for ndir in range(4):
            if dir ^ ndir == 2:
                continue
            if dir ^ ndir == d[s[x][y]]:
                # cost : 0
                if c < dp[x][y][ndir]:
                    dp[x][y][ndir] = c
                    dq.appendleft((c, x, y, ndir))
            else:
                # cost : 1
                if c + 1 < dp[x][y][ndir]:
                    dp[x][y][ndir] = c + 1
                    dq.append((c + 1, x, y, ndir))

    print(dp[h - 1][w - 1][1])


for _ in range(int(input())):
    solve()