ロシアの旗 (Russian Flag)
日本語
Language
Contribute a translation- Time limit
- 10000 ms
- Memory limit
- 256 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
K 理事長はロシアで開催される IOI 2016 に合わせて旗を作ることにした．K 理事長はまず倉庫から古い旗を取り出してきた．この旗は \(N\) 行 \(M\) 列のマス目に分けられていて，それぞれのマスには白・青・赤のいずれかの色が塗られている．
K 理事長はこの旗のいくつかのマスを塗り替えてロシアの旗にしようとしている．ただし，この問題でいうロシアの旗とは以下のようなものである．
- 上から何行か（\(1\) 行以上）のマスが全て白で塗られている．
- 続く何行か（\(1\) 行以上）のマスが全て青で塗られている．
- それ以外の行（\(1\) 行以上）のマスが全て赤で塗られている．
K 理事長が古い旗をロシアの旗にするために塗り替える必要のあるマスの個数の最小値を求めよ．
Input
入力は \(1 + N\) 行からなる．
\(1\) 行目には，\(2\) つの整数 \(N, M\) (\(3 \leqq N \leqq 50\)，\(3 \leqq M \leqq 50\)) が空白を区切りとして書かれている．これは，旗が \(N\) 行 \(M\) 列のマス目に区切られていることを表す．
続く \(N\) 行にはそれぞれ \(M\) 文字からなる文字列が書かれており，古い旗のマス目に塗られている色の情報を表す．\(N\) 行のうちの \(i\) 行目の \(j\) 文字目 (\(1 \leqq i \leqq N\)，\(1 \leqq j \leqq M\)) は，古い旗のマス目の \(i\) 行目 \(j\) 列目のマスの色を表す W，B，R のいずれかの文字である． W は白，B は青，R は赤を表す．
Output
K 理事長が古い旗をロシアの旗にするために塗り替える必要のあるマスの個数の最小値を \(1\) 行で出力せよ．
Examples
4 5 WRWRW BWRWB WRWRW RWBWR
11
入出力例 \(1\) において，古い旗には下図のように色が塗られている．
下図において，X の書かれた \(11\) 個のマスを塗り替える．
これにより下図のようなロシアの旗にすることができる．
\(11\) 個未満のマスを塗り替えることではロシアの旗にすることはできないため，\(11\) を出力する．
6 14 WWWWWWWWWWWWWW WBBBWWRRWWBBBW WWBWWRRRRWWBWW BWBWWRRRRWWBWW WBBWWWRRWWBBBW WWWWWWWWWWWWWW
44
入出力例 \(2\) においては，古い旗には下図のように色が塗られている．
Notes
JOI 2016 · JCIOI · CC BY-SA 4.0
Tags
No tags yet