問題概要
$R$行$C$列のグリッド上を, 上下左右の移動を繰り返すことで全て$K$回ずつ訪れることは可能か判定しなさい.
制約
- $1 \leq R \leq 50$
- $1 \leq C \leq 50$
- $1 \leq K \leq 50$
考察
歪な形じゃないので, $K = 1$のときは自明に可能.
$K > 1$のときは, 始点と終点が隣りあってれば大丈夫.
下のどっちかだったら確実に大丈夫だけど, これ以外に無いことは証明できず… (コンテスト中に証明するの厳しくないか)
左ならC % 2 == 0で, 右ならR % 2 == 0なので, 結局K > 1 or R % 2 == 0 or C % 2 == 0なら可能.
蛇足
ハミルトン閉路みを感じて調べてみたけど, 巡回セールスマン問題の特殊ケースらしいからこのアプローチでは無理そう.
(参考: ハミルトン閉路問題 - Wikipedia)
提出コード(Python3🐍)
class PaintTheRoom:
def canPaintEvenly(self,R,C,K):
return['P','Cannot p'][(K>1)*R%2*C%2]+'aint'