SRM564 Div1 250

問題

w*hのチェスボード上をチェスのナイトが動く。
ナイトツアーとは、任意の場所からスタートし、スタート地点に戻ってくる経路のことを言う。
ここで、同じ場所は何度も通ってよい。
ナイトサーキットのサイズとは、1度でも訪れたチェスのマスのuniq数をいう。
wとhが与えられるので、最大のサイズを答える。

1<=w,h<=45000

考え方

小さいケースで試してみる。
なんども同じところを訪れていいので、dfsなどでできるだけたどれるマスを見つける。

すると、1,2,3とそれ以上の数値の時で法則性が見つかる。
結果的には、
・どちらかが1の時は、うごけないので1
・どちらかが2の時は、(片方の数+1)/2
・どちらも3の時は、8
・それ以外は、w*h
になる。

証明としては、3*4のサイズですべてのマスに訪れることができるので、どちらかの方向に1マス拡張しても、3*4の内部のマスから拡張したマスに移動できるので、結局全部のマスに訪れることができる。なので、3*4以上はすべてのマスにたどれる。
なので、3*3以下のサイズだけ確認すればよい。

反省

試すときは、ちゃんと全探索する。