問題
2行N列の行列が与えられる。各要素はHかSである。以下の3つの操作を行い、すべての要素をHにするための最小の操作回数を求めよ。
- どれか一つの要素を選びXとし、それと隣り合っている要素を一つ選びYとする。Xの要素をYの要素に書き換える。
- 連続する列の要素を選び、隣合う列に書き換える。
- 任意の行を選び、隣り合う片方の行に書き換える。
解法
列のパターンはHH、HS、SH、SSの4パターンとなる。HHしかない場合は0を、SSしかない場合は-1を返す。HHとSSしかない場合は、SSの数が答えとなる。
HSとSHが変化する回数を数える。SH、SHをHHに変えるためには、回の操作が必要となる。SH、HSをすべてSHまたはHSに変えるために必要な操作回数が
となり、SHまたはHSをHHに変えるために1回の操作が必要になる。最後にSSの数を加えることで答えが求まる。
計算量