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; }