## 2013年8月30日

### UVa 707 - Robbery

```#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define PB push_back
#define MP make_pair
using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> PP;

const int dr[5] = {1, 0, -1, 0, 0};
const int dc[5] = {0, 1, 0, -1, 0};

int R, C, T, Case = 1;

bool block[111][111][111];
int times[111][111][111];
bool vis[111][111][111];

inline bool check(int r, int c) {
return (r >= 1) && (r <= R) && (c >= 1) && (c <= C);
}

void solve(PP & init) {
memset(vis, false, sizeof(vis));
vector<P> possible[111];
queue<PP> q;
q.push(init);
while (!q.empty()) {
int t = q.front().first;
P now = q.front().second;
q.pop();
possible[t].PB(now);
if (t == 1) {
continue;
}
for (int d = 0; d < 5; d++) {
int nr = now.first + dr[d], nc = now.second + dc[d];
if (check(nr, nc) && times[t - 1][nr][nc]) {
if (!vis[t - 1][nr][nc]) {
q.push(MP(t - 1, MP(nr, nc)));
vis[t - 1][nr][nc] = true;
}
}
}
}
for (int t = 1; t <= T; t++) {
if (possible[t].size() == 1) {
P & now = possible[t][0];
printf("Time step %d: The robber has been at %d,%d.\n", t, now.second, now.first);
}
}
}

int main() {
while (scanf("%d%d%d", &C, &R, &T) && R) {
memset(block, false, sizeof(block));
printf("Robbery #%d:\n", Case++);
int n;
scanf("%d", &n);
while (n--) {
int t, c1, r1, c2, r2;
scanf("%d%d%d%d%d", &t, &c1, &r1, &c2, &r2);
for (int r = r1; r <= r2; r++) {
for (int c = c1; c <= c2; c++) {
block[t][r][c] = true;
}
}
}
memset(times, 0, sizeof(times));
for (int r = 1; r <= R; r++) {
for (int c = 1; c <= C; c++) {
if (!block[1][r][c]) {
times[1][r][c] = 1;
}
}
}
for (int t = 2; t <= T; t++) {
for (int r = 1; r <= R; r++) {
for (int c = 1; c <= C; c++) {
if (!block[t][r][c]) {
for (int d = 0; d < 5; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (check(nr, nc)) {
times[t][r][c] += times[t - 1][nr][nc];
}
}
}
}
}
}
bool found = false;
for (int t = T; t >= 1 && !found; t--) {
int cnt = 0;
PP last;
for (int r = 1; r <= R; r++) {
for (int c = 1; c <= C; c++) {
if (times[t][r][c]) {
cnt++;
last = MP(t, MP(r, c));
}
}
}
if (cnt == 1) {
found = true;
solve(last);
} else if (!cnt) {
found = true;
puts("The robber has escaped.");
}
}
if (!found) {
puts("Nothing known.");
}
puts("");
}
return 0;
}
```