SRM 371 250pt: SpiralRoute

問題概要

W*H(W,H<5000)のボードがある。こんな風に

nmlkji
oxwvuh
pqrstg
abcdef

ぐるぐるまわって最奥までいくとき、終点の座標を求める問題。

考えたこと

• シミュレーションすれば計算量O(W*H)でギリギリ間に合う。でもメモリが足りない。vectorでboolだと足りるような気もするけど、邪道だよなあ。
• W*Hが共に大きいときは外側の膜を削ればいいだけだし…。
• 書く。通った。

practiceで通ったコード

#include <vector>
using namespace std;


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

struct SpiralRoute {

	vector <int> thronePosition(int width, int length) {
		//大きい所はスキップする
		if(width > 10 && length > 10){
			int cut = min(width-8, length-8) & (~1);
			vector<int> ans = thronePosition(width - cut, length - cut);
			ans[0] += cut/2;
			ans[1] += cut/2;
			return ans;
		}

		//小さい所は愚直にシミュレーション
		vector< vector<bool> > visited(length, vector<bool>(width, false));
		int dir = 0, x = 0, y = 0;
		for(;;){
			visited[y][x] = true;
			int nx = x + dx[dir], ny = y + dy[dir];
			if(!(0<=nx && nx<width && 0<=ny && ny<length && !visited[ny][nx])){
				dir = (dir + 1)%4;
				nx = x + dx[dir], ny = y + dy[dir];
				if(!(0<=nx && nx<width && 0<=ny && ny<length && !visited[ny][nx])){
					vector<int> ret(2);
					ret[0] = x;
					ret[1] = y;
					return ret;
				}
			}
			x = nx;
			y = ny;
		}

	}

};