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

沒有留言:

張貼留言