第19回日本情報オリンピック　二次予選

2019年12月12日
情報オリンピック日本委員会

問題文

JOI 君は文化祭でのクラスの出し物を宣伝するため，ポスターを作った．そのポスターは N 行 N 列のマス目の形をしており，各マスは赤，緑，青のいずれかの色で塗られている．ポスターの上から i 行目，左から j 列目 (1 ≦ i ≦ N，1 ≦ j ≦ N) にあるマスの色は，S_i,j= `R' のとき赤色，S<sub>i,j</sub>= `G' のとき緑色，S_i,j= `B' のとき青色である．

しかし，このポスターにクラスのみんなは満足してはくれなかった．話し合いの結果，マス目の形は変えずに色の配置を変えることで，新しいポスターを作ることに決まった．新しいポスターの上から i 行目，左から j 列目 (1 ≦ i ≦ N，1 ≦ j ≦ N) にあるマスの色は，T_i,j= `R' のとき赤色，T<sub>i,j</sub>= `G' のとき緑色，_i,j= `B' のとき青色となるようにする．

JOI 君は今あるポスターに以下のいずれかの作業を繰り返し行うことで，新しいポスターを作ることにした．

• マスを一つ選び，そのマスの色を好きな色に塗りなおす．
• ポスター全体を 90° 時計回りに回転させる．このとき，もともと上から i 行目，左から j 列目 (1 ≦ i ≦ N，1 ≦ j ≦ N) にあるマスは，上から j 行目，左から N-i+1 列目にあるマスに移動する．
• ポスター全体を 90° 反時計回りに回転させる．このとき，もともと上から i 行目，左から j 列目 (1 ≦ i ≦ N，1 ≦ j ≦ N) にあるマスは，上から N-j+1 行目，左から i 列目にあるマスに移動する．

JOI 君はどの作業をするにも 1 分かかる．JOI 君が作ったポスター，新しく作るポスターの情報が与えられたとき，JOI 君が新しいポスターを作るのに最短で何分かかるかを求めるプログラムを作成せよ．

制約

• 1 ≦ N ≦ 500．
• S_i,j は `R'，`G'，`B' のいずれかである．
• T<sub>i,j</sub> は `R'，`G'，`B' のいずれかである．

入力

入力は以下の形式で標準入力から与えられる．
N
S_1,1 … S_1,N
:
S_N,1 … S_N,N
T_1,1 … T_1,N
:
T_N,1 … T_N,N

出力

新しいポスターを作るのに最短で何分かかるかを 1 行で出力せよ．

入出力例

入力例 1
3
RRR
GGG
BBB
RRR
RRR
RRR

出力例 1
6

• 2 行目と 3 行目にあるマス目をすべて赤色に塗りかえればよい．これには 6 分かかる．

入力例 2
3
RRR
GGG
BBB
RGB
RGB
RGB

出力例 2
1

• ポスター全体を 90° 反時計回りに回転させればよい．これには 1 分かかる．

入力例 3
6
RRRBBB
RRRBBB
RRRBBB
GGGRRG
GGGRRG
GGGBBR
RRRGGG
RRRGGG
RRRGGG
BBBRRB
BBBRRB
BBBGGR

出力例 3
10