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