http://acm.pku.edu.cn/JudgeOnline/problem?id=1104
Код:
#include <stdio.h>
#include <stdlib.h>
char poss[102][102][102];
int ex[102], ey[102];
int size_x, size_y, time;
int neigbour_possible(int x, int y, int t) {
return poss[x-1][y][t] || poss[x+1][y][t] || poss[x][y][t] ||
poss[x][y-1][t] || poss[x][y+1][t];
}
void calc_step(int t1, int t2) {
int x, y;
for (x = 1; x <= size_x; x++)
for (y = 1; y <= size_y; y++) {
if (!neigbour_possible(x, y, t1))
poss[x][y][t2] = 0;
}
}
int main() {
int cnt = 1;
int x, y, t, i, n;
int x1, y1, x2, y2;
int possible, nothing_known;
while (1) {
scanf("%d%d%d%d", &size_x, &size_y, &time, &n);
if (size_x == 0) break;
for (x = 0; x <= size_x+1; x++)
for (y = 0; y <= size_y+1; y++)
for (t = 1; t <= time; t++)
if (x == 0 || y == 0 || x > size_x || y > size_y)
poss[x][y][t] = 0;
else
poss[x][y][t] = 1;
for (i = 0; i < n; i++) {
scanf("%d%d%d%d%d", &t, &x1, &y1, &x2, &y2);
for (x = x1; x <= x2; x++)
for (y = y1; y <= y2; y++)
poss[x][y][t] = 0;
}
for (t = 2; t <= time; t++)
calc_step(t - 1, t);
for (t = time - 1; t >= 1; t--)
calc_step(t + 1, t);
possible = 1;
for (t = 1; t <= time; t++) {
ex[t] = -42;
for (x = 1; x <= size_x; x++)
for (y = 1; y <= size_y; y++)
if (poss[x][y][t]) {
if (ex[t] == -42) {
ex[t] = x;
ey[t] = y;
}
else ex[t] = -1;
}
if (ex[t] == -42) possible = 0;
}
printf("Robbery #%d:\n", cnt++);
if (possible) {
nothing_known = 1;
for (t = 1; t <= time; t++)
if (ex[t] != -1) {
printf("Time step %d: The robber has been at %d,%d.\n",
t, ex[t], ey[t]);
nothing_known = 0;
}
if (nothing_known) printf("Nothing known.\n");
printf("\n");
} else
printf("The robber has escaped.\n\n");
}
return 0;
}