問題G Hot Dogs in Manhattan

• 問題文(COJ 2282)

解法

解説に書いてあるので省略。

コード

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;
const int INF = 1e+8;
const int dx[4] = {0,0,-1,1};
const int dy[4] = {-1,1,0,0};
int w, h, n;
// d[y][x] := (x,y)のプライバシー値
int d[1001][1001];

bool f(int mid){
	vector<int> xleft(h), xright(h);
	for(int y = 0 ; y < h ; y++ ){
		xleft[y] = xright[y] = -1;
		for(int x = 0 ; x < w ; x++ ){
			if( d[y][x] >= mid ){
				if( xleft[y] == -1 ){
					xleft[y] = x;
				}
				xright[y] = x;
			}
		}
	}
	
	for(int y = 0 ; y < h ; y++ ){
		if( xleft[y] == -1 ) continue;
		
		for(int x = y ; x < h ; x++){
			if( xleft[x] == -1 ) continue;
			
			if( abs(xleft[y] - xright[x]) + (x - y) >= mid ){
				return true;
			}
			if( abs(xright[y] - xleft[x]) + (x - y) >= mid ){
				return true;
			}
		}
	}
	return false;
}

int main(){
	int T;
	cin >> T;
	for(int t = 0 ; t < T ; t++ ){
		cin >> n >> w >> h;
		
		// 初期化
		for(int y = 0 ; y < h ; y++ ) fill(d[y], d[y] + w, INF);
		
		queue<P> q;
		for(int i = 0 ; i < n ; i++ ){
			int x, y;
			cin >> x >> y;
			d[y][x] = 0;
			q.push( P(x, y) );
		}
		
		// BFSで交差点ごとに既存のスタンドからの距離の最小値を求める
		while( !q.empty() ){
			int x = q.front().first, y = q.front().second; q.pop();
		
			for(int i = 0 ; i < 4 ; i++ ){
				int mx = x + dx[i], my = y + dy[i];
				if( mx < 0 || my < 0 || w <= mx || h <= my ) continue;
				
				if( d[y][x] + 1 < d[my][mx] ){
					d[my][mx] = d[y][x] + 1;
					q.push( P(mx, my) );
				}
			}
		}
		
		// 二分探索
		int low = 0, high = w + h;
		while( low <= high ){
			int mid = (low + high) / 2;
			if( f(mid) ){
				low = mid + 1;
			}else{
				high = mid - 1;
			}
		}
		cout << high << endl;
	}
}