SRM564 Div1 Easy - KnightCircuit2
チェスサークルの力を発揮
問題
h*wのチェス盤がある
好きなマスにナイトを置いて好きなだけ動かすとき、ナイトが通れるマスの最大値を求めよ
1 <= h, w <= 45000
解法
h<=wとする
h=1: 一度も動けないから答えはスタート地点の1マスのみ
h=2: ジグザグに動けばceil(w/2)マス通れる
h=3かつw=3: 中央以外の8マスは全部通れる
その他: 全マス通れる
class KnightCircuit2 { public: int maxSize(int w, int h) { if (h>w) swap(h,w); if (h==1) return 1; if (h==2) return (w+1)/2; if (h==3 && w==3) return 8; return h*w; } };
https://community.topcoder.com/stat?c=problem_statement&pm=10968&rd=15186