第 16 回 日本情報オリンピック　模擬予選 ４

2016年12月10日
E869120, square1001

問題

JOI 君は日本で開催される IOI 2018 に合わせて旗を作ることにした. JOI 君はまず倉庫から古い旗を取り出してきた. この旗は H 行 W 列のマス目に分けられていて, 長方形状である. また, それぞれのマスには白か赤のいずれかの色が塗られている.

JOI 君はこの旗のいくつかのマスを塗り替えて日本国旗にしようとしている. ただし, この問題でいう日本国旗とは以下のようなものである.

• 国旗に垂直な直線と水平な直線について線対称となっている.
• 任意の赤のマスから, 他の赤のマスへ, 辺を共有している赤のマスを辿ってたどり着くことが出来る.また, 赤のマスによって囲まれる白のマスは存在しない.
• 1 ≦ i ≦ H / 2 - 1 を満たす整数 i について, 国旗の i 行目に含まれている赤のマスの個数は, 国旗の i + 1 行目に含まれている赤のマスの個数以下である.
• 各行について, 赤マスは一つのまとまりとなって配置されている. すなわち, ある行に赤マスがあるのであれば, その行の赤マスがある左端の列を L 列目, 右端の列を R 列目として, L ≦ i ≦ R を満たすすべての i について, i 列目は赤マスとなっている.
• 国旗の 1 行目, 1 列目, H 行目, および W 列目に赤のマスが含まれない.

下図にいくつかの国旗の例を示す.

図 (A) と図 (B) は正しい日本国旗の例である. 図 (B) のように, 1 つも赤のマスが存在しない旗も日本国旗として認められる.

図 (C), (D), (E), (F) は正しくない日本国旗の例である. 図 (C) では, 国旗に垂直な直線について線対称になっていない. 図 (D) では, たとえば 2 行 3 列目の赤マスから 3 行 2 列目の赤マスへ, 辺を共有している赤マスだけを辿ってたどり着くことが出来ない. 図 (E) では, 赤のマスに囲まれている白のマスの領域が存在する. 図 (F) では, 1 列目及び 6 列目に赤のマスが含まれている.

JOI 君が古い旗を日本国旗にするために塗り替える必要のあるマスの個数の最小値を求めよ.

入力

入力は 1 + H 行からなる.

1 行目には，2 つの整数 H, W (2 ≦ H ≦ 100, 2 ≦ W ≦ 100) が空白を区切りとして書かれている. これは, 旗が H 行 W 列のマス目に区切られていることを表す. ここで, H と W は偶数であることが保証されている.

続く H 行にはそれぞれ W 文字からなる文字列が書かれており, 古い旗のマス目に塗られている色の情報を表す. H 行のうちの i 行目の j 文字目 (1 ≦ i ≦ H, 1 ≦ j ≦ W) は, 古い旗のマス目の i 行目 j 列目のマスの色を表す 'W', 'R' のいずれかの文字である. 'W' は白, 'R' は赤を表す.

出力

JOI 君が古い旗を日本国旗にするために塗り替える必要のあるマスの個数の最小値を 1 行で出力せよ.

入出力例

6 6
WRRWRR
RWRWWR
RWRWRR
RRRWRR
WWRRWW
WWWRWR




  

10 10
RRRRRRRRRR
RRRRRRRRRR
RRRRRRRRRR
RRRRRRRRRR
WWWWWWWWWW
WWWWWWWWWW
RRRRRRRRRR
RRRRRRRRRR
RRRRRRRRRR
RRRRRRRRRR
  

16
   

48
   

入出力例 1 において, 古い旗には下図のように色が塗られている.

下図において, 'X' の書かれた 16 個のマスを塗り替える.

これにより下図のような日本国旗にすることができる.

※各入出力例のデータは，右クリック等によりファイルに保存して利用可能です．

採点用データ