2013年2月28日

UVa 10496 - Collecting Beepers


#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define MP make_pair
using namespace std;

typedef pair<int, int> P;
typedef set<P> S;
typedef pair<P, S> PP;
const int dr[] = {0, 1, 0, -1};
const int dc[] = {1, 0, -1, 0};

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int R, C, sr, sc, n;
    scanf("%d%d%d%d%d", &R, &C, &sr, &sc, &n);
    S s;
    while (n--) {
      int a, b;
      scanf("%d%d", &a, &b);
      s.insert(MP(a, b));
    }
    s.erase(MP(sr, sc));
    queue<PP> q;
    map<PP, int> dis;
    q.push(MP(MP(sr, sc), s));
    dis[MP(MP(sr, sc), s)] = 0;
    int min = 2e9;
    while (!q.empty()) {
      int r = q.front().first.first, c = q.front().first.second;
      s = q.front().second;
      int d = dis[q.front()];
      q.pop();
      if (!s.size()) {
        d = d + (int)abs(sr - r) + (int)abs(sc - c);
        min = d < min ? d : min;
        continue;
      }
      int i;
      for (i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (nr && nr <= R && nc && nc <= C) {
          PP next;
          if (s.count(MP(nr, nc))) {
            S ns = s;
            ns.erase(MP(nr, nc));
            next = MP(MP(nr, nc), ns);
          } else {
            next = MP(MP(nr, nc), s);
          }
          if (!dis.count(next)) {
            q.push(next);
            dis[next] = d + 1;
          }
        }
      }
    }
    printf("The shortest path has length %d\n", min);
  }
  return 0;
}

沒有留言:

張貼留言