POJ: Evacuation

3
5 5
XXDXX
X...X
D...X
X...D
XXXXX
5 12
XXXXXXXXXXXX
X..........D
X.XXXXXXXXXX
X..........X
XXXXXXXXXXXX
5 5
XDXXX
X.X.D
XX.XX
D.X.X
XXXDX
3
21
impossible
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;#define ROW 13
#define COL 13
#define MAXITEMS ((ROW) * (COL))
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int distance2door[ROW][COL][ROW][COL];
vector<pair<int, int> > doors;
vector<pair<int, int> > persons;
char fields[ROW][COL];
vector<int> G[MAXITEMS * MAXITEMS];
int match[MAXITEMS * MAXITEMS];
bool used[MAXITEMS * MAXITEMS];
int V;
void add_adge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
bool dfs(int v) {
used[v] = true;
for (int i = 0; i < G[v].size(); ++i) {
int u = G[v][i];
int w = match[u];
if (w < 0 || !used[w] && dfs(w)) {
match[v] = u;
match[u] = v;
return true;
}
}
return false;
}
void computeDistance(int x, int y, int d[ROW][COL]) {
queue<pair<int, int> > q;
d[x][y] = 0;
q.push(make_pair(x, y));
while (!q.empty()) {
int i = q.front().first;
int j = q.front().second;
q.pop();
for (int k = 0; k < 4; ++k) {
int px = i + dx[k];
int py = j + dy[k];
if (px >= 0 && px < ROW && py >= 0 && py < COL && d[px][py] == -1 && fields[px][py] == '.') {
d[px][py] = d[i][j] + 1;
q.push(make_pair(px, py));
}
}
}
}
int main(int argc, char *argv[]) {
int times;
scanf("%d", &times);
while (times--) {
int rows, cols;
doors.clear();
persons.clear();
memset(distance2door, -1, sizeof(distance2door));
getchar();
scanf("%d%d", &rows, &cols);
for (int i = 0; i < rows; ++i) {
getchar();
for (int j = 0; j < cols; ++j) {
char c;
scanf("%c", &fields[i][j]);
if (fields[i][j] == 'D') {
doors.push_back(make_pair(i,j));
} else if (fields[i][j] == '.') {
persons.push_back(make_pair(i,j));
}
}
}
for (int i = 0; i < doors.size(); ++i)
computeDistance(doors[i].first, doors[i].second, distance2door[doors[i].first][doors[i].second]);
int d = doors.size();
int p = persons.size();
for (int v = 0; v < rows * cols * doors.size(); ++v) G[v].clear();
for (int i = 0; i < d; ++i) {
for (int j = 0; j < p; ++j) {
if (distance2door[doors[i].first][doors[i].second][persons[j].first][persons[j].second] >= 0) {
for (int k = distance2door[doors[i].first][doors[i].second][persons[j].first][persons[j].second]; k <= rows * cols; ++k)
add_adge((k-1) * d + i, rows * cols * d + j);
}
}
}
if (persons.size() == 0) {
printf("0\n");
} else {
int num = 0;
memset(match, -1, sizeof(match));
for (int v = 0; v < rows * cols * doors.size(); ++v) {
memset(used, 0, sizeof(used));
if (dfs(v)) {
if (++num == persons.size()) {
printf("%d\n", v / (int)doors.size() + 1);
break;
}
}
}
if (num != persons.size()) printf("impossible\n");
}
}
return 0;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store