AOJ 0542 認証レベル

AOJ グラフ理論

以前まったく分からなかったが、久しぶりにやってみると解法がすぐ思いついて驚いた。

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0542

解法
ある事務所で認証レベルを順番にあげていって、入れる部屋の総数とレベルの表をつくる
最初のサンプルでやってみると

5
2 2 1 2
9 5
1 17
3 2 2 1
6 1 20
8 18 3

1つ目の事務所について

レベル: 0  1  9 17
部屋　: 0  1  3  4

2つ目の事務所について

レベル: 0  1  6  8 18 20
部屋　: 0  1  2  3  5  6

とする。
あとは最初の事務所のレベルをあげていって、2つ目の事務所の部屋数を二分探索すればよい

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> LP;
const int MAX_HW = 500;
int R, H[2], W[2], X[2], Y[2], office[2][MAX_HW][MAX_HW];
vector<int> room_n[2];
vector<int> level[2];
bool visited[2][MAX_HW][MAX_HW];
void init(int k){
	scanf("%d %d %d %d", &W[k], &H[k], &X[k], &Y[k]);
	room_n[k].clear();
	level[k].clear();
	X[k]--; Y[k]--;
	for(int i = 0; i < H[k]; i++)
		for(int j = 0; j < W[k]; j++){
			scanf("%d", &office[k][i][j]);
			visited[k][i][j] = false;
		}
}
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int dfs(int k, int x, int y, int l, priority_queue<LP, vector<LP>, greater<LP> > &Q){
	visited[k][y][x] = true;
	int ret = 1;
	for(int i = 0; i < 4; i++){
		int nx = x + dx[i], ny = y + dy[i];
		if(0 <= nx && nx < W[k] && 0 <= ny && ny < H[k] && !visited[k][ny][nx]){
			if(office[k][ny][nx] <= l)
				ret += dfs(k, nx, ny, l, Q);
			else
				Q.push(LP(office[k][ny][nx], P(nx, ny)));
		}
	}
	return ret;
}
void make_table(int k){
	priority_queue<LP, vector<LP>, greater<LP> > Q;
	room_n[k].push_back(0);
	level[k].push_back(0);
	Q.push(LP(1, P(X[k], Y[k])));
	while(!Q.empty()){
		LP lp = Q.top(); Q.pop();
		int lev = lp.first, x = lp.second.first, y = lp.second.second;
		if(visited[k][y][x]) continue;
		room_n[k].push_back(dfs(k, x, y, lev, Q) + room_n[k][room_n[k].size() - 1]);
		level[k].push_back(lev);
	}
}
int main(){
	while(true){
		scanf("%d", &R);
		if(R == 0) return 0;
		init(0); init(1);
		make_table(0); make_table(1);
		int ans = 500000000;
		for(int i = 0; i < level[0].size(); i++){
			int r0 = room_n[0][i];
			int j = distance(room_n[1].begin(), lower_bound(room_n[1].begin(), room_n[1].end(), R - r0));
			if(j < room_n[1].size())
				ans = min(ans, level[0][i] + level[1][j]);
			}
		printf("%d\n", ans);
	}
	return 0;
}