JOI2013春合宿day3 山岳救助隊

問題

日本語なので本文参照(http://imoz.jp/data/joi/2013-sp-d3-mountain.pdf


マップから、高さがxであるような点を求める。
マップのそれぞれのマスの高さは異なる。
山の頂点のマスがある。
マップのそれぞれのマスから、頂点から遠くなるほうの隣接するマスは、必ず高さが低い。

制約条件

マップの広さは200x200
マスの高さを調べられる回数は1000回まで。

方針

解説スライドに賢い方法が載ってた。
http://japl.pl/slides/joi/mountain_rescue_team.pdf


自分は、適当に頂点から4方向に二分探索して、ゴールの高さに近いマスを4つ求め、
そこから、ゴールとの差分をペナルティとしてダイクストラした。
こんな感じの嘘解法でも通ってしまった。

ソースコード

bool v[1010][1010];
int dp[1010][1010], cnt;
int ty, tx, goal;
priority_queue<pi> q;
 
int get(int y, int x){
	int &res = dp[y][x];
	if(res > 0) return res;
	if(++cnt > 1000){
		while(1);
		Pinpoint(y + 1, x + 1);
	}
	res = Measure(y + 1, x + 1);
	if(res == goal) Pinpoint(y + 1, x + 1);
	return res;
}
void push(int y, int x){
	if(!v[y][x]) q.push(mp(-abs(goal - get(y, x)), y * 1000 + x));
}
 
void Rescue(int h, int w, int ty, int tx, int goal){
	ty--; tx--;
	::goal = goal;
	::ty = ty; ::tx = tx;
	
	int lo = tx, hi = w, mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		if(get(ty, mid) >= goal) lo = mid;
		else hi = mid;
	}
	push(ty, lo);
	lo = ty, hi = h, mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		if(get(mid, tx) >= goal) lo = mid;
		else hi = mid;
	}
	push(lo, tx);
	
	lo = 0, hi = tx + 1, mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		assert(0 <= mid && mid < w);
		if(get(ty, mid) < goal) lo = mid;
		else hi = mid;
	}
	push(ty, lo);
	lo = 0, hi = ty + 1, mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		assert(0 <= mid && mid < h);
		if(get(mid, tx) < goal) lo = mid;
		else hi = mid;
	}
	push(lo, tx);
	
	while(!q.empty()){
		int y = q.top().second / 1000, x = q.top().second % 1000;
		q.pop();
		if(v[y][x]) continue;
		v[y][x] = 1;
		if(get(y, x) == goal){
			Pinpoint(y + 1, x + 1);
		}
		
		rep(d, 4){
			const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
			int ny = y + dy[d], nx = x + dx[d];
			if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
			if(v[ny][nx]) continue;
			
			if((get(y, x) > goal) == (abs(ny - ty) + abs(nx - tx) < abs(y - ty) + abs(x - tx)))
			continue;
			q.push(mp(-abs(goal - get(ny, nx)), ny * 1000 + nx));
		}
	}
	while(1);
	rep(i, h) rep(j, w) if(!v[i][j]) Pinpoint(i + 1, j + 1);
}