TopCoder SRM 564 Div1 Easy KnightCircuit2

問題

w x hのチェス番がある。
好きなマスにナイトを置いて、自由に動かす。
同じマスを何回通ってもよい。

このとき、ナイトが一度以上行けたマスの数は最大でいくつになるか、求めよ。

制約条件

w, h≦45000

方針

サンプルより100 x 100のときはすべてのマスにいけることがわかる。
なので、w≧100かつh≧100のときは全部のマスに行ける。

w≦100またはh≦100のとき、
w * h≦4500000なので、全探索して間に合う。

ソースコード

const int dy[] = {-2, -2, -1, 1, 2, 2, 1, -1}, dx[] = {-1, 1, 2, 2, 1, -1, -2, -2};

int p[10000], sz[10000];
int root(int x){
	if(x == p[x]) return x;
	return p[x] = root(p[x]);
}

class KnightCircuit2 {
	public:
	int maxSize(int w, int h) {
		if(w < h) swap(w, h);
		if(h == 1) return 1;
		if(h == 2){
			return (w + 1) / 2;
		}
		if(w < 100 && h < 100) return calc(w, h);
		return w * h;
	}
	int calc(int w, int h){
		rep(i, h * w) p[i] = i, sz[i] = 1;
		int ans = 0;
		rep(i, h) rep(j, w) rep(d, 8){
			int ny = i + dy[d], nx = j + dx[d];
			if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
			int a = root(ny * w + nx), b = root(i * w + j);
			if(a != b){
				p[b] = a;
				sz[a] += sz[b];
			}
		}
		rep(i, h * w) ans = max(ans, sz[i]);
		return ans;
	}
};