SRM380 Div2 500

問題

ケガしたナイトがheight*widthの大きさのチェス盤の左下においてある。健康なナイトとは違って、このケガしたナイトは、「2セル上がって1セル右へ」「1セル上がって2セル右へ」「1セル下がって2セル右へ」「2セル下がって右へ」のいずれかの動きしかできない。
このナイトがたどることができるセルの最大値を求める。
ただし、4回より少ない移動までは特に制約はないが、4回以上の移動をする場合は上記の4つすべての動きを1度はしなければならない。

考え方

実際に十分大きなマス目を書いて、5ターンほどナイトの動きを書いてみる。
そうすると、右下方向に行く場合すべての手順を使って少ないwidthで移動することができることがわかる。なので、十分なheightがあれば、右下近くで移動するのがよいのがわかる。

heightが十分ない場合についても場合わけすると、

• h>=3のとき、
  • w=1,2,3なら、答えはそれぞれ1,2,3
  • w=4,5,6なら、答えは4
  • w>6なら、答えはw-2
• h==2のとき、
  • w=1,2なら、答えは1
  • w=3,4なら、答えは2
  • w=5,6なら、答えは3
  • w>6なら、答えは4
• それ以外は、答えは1