POJ 3057「Evacuation」は、壁で区切られた部屋から各出口につき1秒に1人ずつ脱出する問題です。Xは壁、.は最初に1人がいるマス、Dは出口です。毎秒、上下左右に1マス移動でき、全員が出る最小時間を求めます。
原題では内部の1マスに複数人がいても構いません。人数制限は出口に適用されます。出口に着けば脱出完了なので、別の領域への通路としては使えません。下の再生は歩行経路ではなく、出口を通過する時刻表を示します。
現在の状態
解法の考え方
- BFSで距離を求める：各出口から内部のマスを探索し、人pが出口dに到着できる最短時間dist[d][p]を求めます。
- 制限時間Tを決める：右側の頂点を（出口、1秒）、（出口、2秒）…（出口、T秒）とします。
- 二部グラフを作る：dist[d][p] ≤ tなら、人pを（出口d、時刻t）の枠につなぎます。到達できない出口にはつなぎません。
- DFSで割り当て直す：使用済みの枠なら、その人を別の枠へ移せるか再帰的に調べます。全員に異なる枠があればT秒で可能です。
- 最小のTを探す：可能な時間より長ければ引き続き可能なので、二分探索を使えます。
ここでDFSが探索するのは部屋の移動経路ではなく割り当てのグラフです。P1が1秒でD1とD2に着けて、P2はD1だけに着ける場合を考えます。P1を先にD1へ入れても、DFSでP1をD2へ移し、P2にD1を割り当てられます。
出口1つの例には8人います。最も遠い人の最短距離は5秒ですが、出口の処理に8秒かかります。最小時間を表示した後、Tを1減らして割り当て人数の変化を確かめてください。
マッチングは、各人に到達可能な時刻を与え、同じ出口・同じ秒の重複を防ぎます。内部で待機し同じマスを共有できるので、この予定は実現できます。逆に実際の脱出予定もマッチングになるため、全員の割り当てとT秒以内の脱出は同値です。
計算量と注意点
人数をP、出口数をD、マップをR × C、各人の最寄りの到達可能な出口までの距離の最大値をLとします。どの出口にも着けない人がいればimpossibleです。それ以外はmax(L, ceil(P/D))からU = L + P - 1まで探索します。L秒までに各自が最寄りの出口付近へ進み、最大P人を順に通せばU秒で十分です。
距離計算はO(DRC)です。T秒のグラフの辺数をETとすると、DFSマッチングはO(P ET)で、ET ≤ PDTです。全体の時間計算量の上限はO(DRC + P EU log(U+1))、追加空間はO(RC + DP + EU + DU)です。
最寄りの出口だけに向かわせたり、最短距離の最大値だけを答えにしたりすると出口の混雑を見落とします。内部のマスも1人に制限する別問題には、このモデルは使えません。下はこの条件に合わせたC++コードで、ブラウザーの実験は小さな例を使っています。
この解説のために作成したコード
C++ (C++98)
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;
struct Evacuation {
vector<pair<int, int> > people, doors;
vector<vector<int> > distance, edges;
vector<int> owner, seen;
int stamp;
bool augment(int person) {
for (int i = 0; i < (int)edges[person].size(); ++i) {
int slot = edges[person][i];
if (seen[slot] == stamp) continue;
seen[slot] = stamp;
if (owner[slot] == -1 || augment(owner[slot])) {
owner[slot] = person;
return true;
}
}
return false;
}
bool feasible(int limit) {
int p = people.size(), d = doors.size();
edges.assign(p, vector<int>());
for (int person = 0; person < p; ++person)
for (int door = 0; door < d; ++door)
if (distance[door][person] != -1)
for (int t = distance[door][person]; t <= limit; ++t)
edges[person].push_back((t - 1) * d + door);
owner.assign(d * limit, -1);
seen.assign(d * limit, 0);
stamp = 0;
for (int person = 0; person < p; ++person) {
++stamp;
if (!augment(person)) return false;
}
return true;
}
int solve(const vector<string>& grid) {
int h = grid.size(), w = grid[0].size();
for (int r = 0; r < h; ++r) for (int c = 0; c < w; ++c) {
if (grid[r][c] == '.') people.push_back(make_pair(r, c));
if (grid[r][c] == 'D') doors.push_back(make_pair(r, c));
}
int p = people.size(), d = doors.size();
if (p == 0) return 0;
if (d == 0) return -1;
distance.assign(d, vector<int>(p, -1));
int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
for (int door = 0; door < d; ++door) {
vector<vector<int> > dist(h, vector<int>(w, -1));
queue<pair<int, int> > q;
q.push(doors[door]);
dist[doors[door].first][doors[door].second] = 0;
while (!q.empty()) {
int r = q.front().first, c = q.front().second;
q.pop();
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
if (grid[nr][nc] != '.' || dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[r][c] + 1;
q.push(make_pair(nr, nc));
}
}
for (int person = 0; person < p; ++person)
distance[door][person] = dist[people[person].first][people[person].second];
}
int farthest = 0;
for (int person = 0; person < p; ++person) {
int nearest = h * w + 1;
for (int door = 0; door < d; ++door)
if (distance[door][person] != -1)
nearest = min(nearest, distance[door][person]);
if (nearest == h * w + 1) return -1;
farthest = max(farthest, nearest);
}
int low = max(farthest, (p + d - 1) / d), high = farthest + p - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (feasible(mid)) high = mid;
else low = mid + 1;
}
return low;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int cases;
cin >> cases;
while (cases--) {
int h, w;
cin >> h >> w;
vector<string> grid(h);
for (int r = 0; r < h; ++r) cin >> grid[r];
Evacuation solver;
int answer = solver.solve(grid);
if (answer < 0) cout << "impossible\n";
else cout << answer << '\n';
}
}