SRM 236 DIV1 Hard Parking

問題 Editorial

問題

H*Wのマップparkが与えられる。
parkはそれぞれ '.': 空白, 'X': 壁, 'C': 車, 'P': 駐車場。
車を全て駐車場に駐車させたい。1つの駐車場に1台までしか駐車できない。
車は同じマスを複数通ることができる(駐車場のマスでも、そこを通るだけなら複数台通れる)。
車は上下左右に移動させることができて、そのたびに単位時間がかかる。
車を全て駐車場に駐車させる時の車の移動時間の最大を最小化せよ

• 1 <= H, W <= 50
• 0 <= 車の数, 駐車場の数 <= 100

解答

まず各(車*駐車場)に対して最小距離を求めておく。
ある最大距離mid以下で全ての車が移動できるかは、(車, 駐車場, 距離がmid以下の(車,駐車場))という二部グラフを作り、マッチングサイズが車の数かどうかで判定できる。
あとは最大距離で二分探索する。

コメント

二分探索の初期lowerを0にして境界でミスった。ひどい。最終的にupperを返す時はlowerを-1しろ！
あと、境界条件のテストをきちんとしろ！
どんな問題でも、答えが0になるケースは絶対テストしろ！

コード

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;

vector<bool> done;
vector<int> match;
vector<vector<int> >e;
bool augment(int i) {
	if(done[i]) return false;
	else done[i] = true;
	each(j, e[i]) if(match[*j] == -1 || augment(match[*j])) {
		match[*j] = i;
		return true;
	}
	return false;
}

struct Parking {
	int minTime(vector <string> park) {
		int h = park.size(), w = park[0].size();
		int n = 0, m = 0; vpii cars, parkings;
		rep(i, h) rep(j, w) {
			if(park[i][j] == 'C') cars.pb(mp(i, j)), ++ n;
			else if(park[i][j] == 'P') parkings.pb(mp(i, j)), ++m;
		}
		static int dists[100][100];
		rep(i, n) {
			static int dist[50][50];
			mset(dist, INF);
			int x = 0;
			vpii q, next;
			next.pb(cars[i]);
			while(!next.empty()) {
				q.swap(next);
				while(!q.empty()) {
					pii p = q.back(); q.pop_back();
					if(dist[p.first][p.second] <= x) continue;
					dist[p.first][p.second] = x;
					static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
					rep(d, 4) {
						int yy = p.first + dy[d], xx = p.second + dx[d];
						if(0<=yy&&yy<h&&0<=xx&&xx<w&&park[yy][xx] != 'X') next.pb(mp(yy, xx));
					}
				}
				++ x;
			}
			rep(j, m) {
				dists[i][j] = dist[parkings[j].first][parkings[j].second];
			}
		}
		int l = -1, u = 2501; bool ok = false;
		while(u - l > 1) {
			int mid = (l + u) / 2;
			e = vector<vector<int> >(n);
			rep(i, n) rep(j, m) if(dists[i][j] <= mid) e[i].pb(j);
			match = vector<int>(m, -1);
			int count = 0;
			rep(i, n) {
				done = vector<bool>(n, false);
				if(augment(i)) ++ count;
			}
			if(count == n) u = mid, ok = true;
			else l = mid;
		}
		return !ok ? -1 : u;
	}
};