POJ 3057 “Evacuation” places people in a room divided by walls. X is a wall, . a cell initially occupied by one person, and D a door. People move one orthogonal cell per second, and each door lets one person leave per second. Find the earliest time everyone can leave.
The original problem allows multiple people in an interior cell. Capacity is restricted at doors. Reaching a door means exiting; a door cannot serve as a passage into another region. The playback below shows exit appointments, not walking trajectories.
Current state
How the solution works
- Measure distances with BFS: search from each door through interior cells to get dist[d][p], the earliest arrival of person p at door d.
- Ask about a deadline T: create right-side vertices for (door, second 1), (door, second 2), up to second T.
- Build a bipartite graph: connect person p to slot (d, t) when dist[d][p] ≤ t. Unreachable doors get no edge.
- Reassign with DFS: if a slot is occupied, recursively try moving its current owner elsewhere. A matching covering every person makes T feasible.
- Search for the earliest T: feasibility is monotone, so use binary search.
DFS explores the assignment graph, not the room’s walking paths. Suppose P1 can reach D1 or D2 at second 1, while P2 can reach only D1. Even if P1 initially takes D1, an augmenting path can move P1 to D2 and give D1 to P2.
The one-door preset has eight people. The farthest shortest distance is five seconds, but the door needs eight seconds to admit everyone. Show the minimum time, then reduce T by one to inspect the lost assignment.
A matching gives each person a reachable exit time without duplicate door-time slots. Waiting and shared interior cells make that schedule realizable. Conversely, any valid evacuation defines such a matching, so covering everyone is equivalent to meeting the deadline.
Complexity and pitfalls
Let P be the number of people, D the doors, R × C the grid, and L the largest distance to a nearest reachable door. If someone has no reachable door, return impossible. Otherwise search from max(L, ceil(P/D)) to U = L + P - 1. Everyone can reach a nearest door by L; processing at most P people sequentially then finishes by U.
Distances cost O(DRC). With ET edges at deadline T, DFS matching costs O(P ET), where ET ≤ PDT. A total time bound is O(DRC + P EU log(U+1)), with O(RC + DP + EU + DU) extra space.
Always choosing the nearest door or returning only the largest shortest distance misses door congestion. This model does not apply to variants allowing only one person per interior cell. The C++ solution below follows the stated model; the browser experiment uses small examples.
Solution code written for this guide
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';
}
}