2013年8月1日

UVa 10977 - Enchanted Forest

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

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

int main() {
  int R, C;
  while (scanf("%d%d", &R, &C) && R || C) {
    int n, m;
    scanf("%d", &n);
    bool block[201][201] = {};
    while (n--) {
      int r, c;
      scanf("%d%d", &r, &c);
      block[r][c] = true;
    }
    scanf("%d", &m);
    while (m--) {
      int r, c, l;
      scanf("%d%d%d", &r, &c, &l);
      for (int i = r - l; i <= r + l; i++) {
        for (int j = c - l; j <= c + l; j++) {
          if (((i - r) * (i - r) + (j - c) * (j - c) <= l * l) && i > 0 && i <= R && j > 0 && j <= C) {
            block[i][j] = true;
          }
        }
      }
    }
    queue<P> q;
    q.push(MP(1, 1));
    int len[201][201] = {};
    bool find = false;
    while (!q.empty()) {
      P now = q.front();
      int r = now.first, c = now.second, l = len[r][c];
      q.pop();
      if (r == R && c == C) {
        printf("%d\n", l);
        find = true;
        break;
      }
      for (int i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (!len[nr][nc] && !block[nr][nc] && nr > 0 && nr <= R && nc > 0 && nc <= C) {
          if (nr == 1 && nc == 1) {
            continue;
          }
          q.push(MP(nr, nc));
          len[nr][nc] = l + 1;
        }
      }
    }
    if (!find) {
      puts("Impossible.");
    }
  }
  return 0;
}

沒有留言:

張貼留言