まず、以下の問題を考えます。

\(4N\) 個のマスが円環状に並んでいる。\(4N\) マスのうち \(2N\) マスにイチゴが乗っている。連続する \(2N\) マスを含まれるイチゴがちょうど \(N\) 個になるように選ぶ方法を一つ見つけよ。

これには解が必ず存在するので、累積和と全探索を用いて解を見つけることができます。

解が存在することの証明：

マスを適当な場所から時計回りに順にマス \(1,2,\ldots,4N\) とします。

\(f(i)\) をマス \(i\) からマス \(i+2N\) までに含まれるイチゴの数とします。\(f(i)=N\) となる \(i\) の存在を言えば良いです。

\(4N\) マスの中にイチゴは \(2N\) 個あるので、\(f(1)+f(2N+1)=2N\) が成り立ちます。\(f(1)=N\) ならば条件を満たします。\(f(1)<N\) の場合、\(|f(i+1)-f(i)|\le 1\) であることと \(f(1) < N < f(2N+1)\) であることから \(f(2),f(3),\ldots,f(2N)\) の中に \(N\) となるものが存在します。\(f(1)>N\) の場合も同様です。

以上を踏まえると、\(2H\times 2W\) のグリッドを全てのマスを \(1\) 回ずつ回りながら一周するようなハミルトン閉路を \(1\) つ選び上の全探索を行うことで条件を満たす解を見つけられることが分かります。

そして、そのようなハミルトン閉路は以下のように構築することができます：

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

import sys

input = sys.stdin.readline

for _ in range(int(input())):
    h, w = map(int, input().split())
    s = [input() for _ in range(2 * h)]
    r = []
    c = []
    for j in range(0, 2 * w, 2):
        for i in range(1, 2 * h):
            r.append(i)
            c.append(j)
        for i in reversed(range(1, 2 * h)):
            r.append(i)
            c.append(j + 1)
    for j in reversed(range(2 * w)):
        r.append(0)
        c.append(j)
    a = [0] + [1 if s[r[i]][c[i]] == "o" else -1 for i in range(4 * h * w)]
    for k in range(4 * h * w):
        a[k + 1] += a[k]
    for k in range(2 * h * w):
        if a[2 * h * w + k] == a[k]:
            ans = [["A" for _ in range(2 * w)] for _ in range(2 * h)]
            for kk in range(2 * h * w):
                ans[r[k + kk]][c[k + kk]] = "B"
            for row in ans:
                print("".join(row))
            break

原案：kyopro_friends