#include <cstdio>
#include <cstring>
#include <queue>
#include <ext/hash_set>
#define maxn 22
bool map[maxn][maxn];
using namespace std;
unsigned short n, m, l, swd;
class snak {
private:
unsigned short st;
unsigned char x, y;
public:
inline bool succ() { return x == 1 && y == 1; }
inline unsigned tousg() { return (unsigned)this; }
inline bool move(short u) {
short c1 = 0, c2 = 0;
if (u == 0) --x, c1 = 1;
else if (u == 1) ++x, c1 = -1;
else if (u == 2) --y, c2 = 1;
else if (u == 3) ++y, c2 = -1;
st <<= 2;
st |= u;
if (map[x][y]) return false;
else {
for (int i = 1; i < l; ++i) {
short sx = (st >> (i << 1)) & 3;
if (sx == 0) ++c1;
else if (sx == 1) --c1;
else if (sx == 2) ++c2;
else if (sx == 3) --c2;
if (c1 == 0 && c2 == 0) return false;
}
st &= swd;
return true;
}
}
snak(char, char, char, char) {
st = 0;
int tx, ty, ox, oy;
scanf("%d%d", &tx, &ty);
x = ox = tx; y = oy = ty;
for (short r = 0; r < l - 1; ++r) {
scanf("%d%d", &tx, &ty);
/*if (tx == ox + 1) ; st |= 0 << (r << 1)*/
if (tx == ox - 1) st |= 1 << (r << 1);
else if (ty == oy + 1) st |= 2 << (r << 1);
else if (ty == oy - 1) st |= 3 << (r << 1);
ox = tx; oy = ty;
}
}
};
struct bfs {
snak s;
int d;
bfs(snak s, int d) : s(s), d(d) {}
};
inline void main1(int kase) {
snak ss('c', 'r', 'l', 's');
#define clear(x) memset(x, 0, sizeof(x))
clear(map);
for (int i = 0; i <= m; ++i) map[0][i] = map[n + 1][i] = true;
for (int i = 0; i <= n; ++i) map[i][0] = map[i][m + 1] = true;
int k; scanf("%d", &k);
while (k--) {
int tx, ty; scanf("%d%d", &tx, &ty);
map[tx][ty] = true;
}
queue<bfs> Q;
__gnu_cxx::hash_set<unsigned> sn;
Q.push(bfs(ss, 0)); sn.insert(ss.tousg());
while (!Q.empty()) {
bfs o(Q.front()); Q.pop();
if (o.s.succ()) {
printf("Case %d: %d\n", kase, o.d);
return;
}
for (short m = 0; m < 4; ++m) {
snak al = o.s;
if (al.move(m) && sn.find(al.tousg()) == sn.end()) {
Q.push(bfs(al, o.d + 1));
sn.insert(al.tousg());
}
}
}
printf("Case %d: -1\n", kase);
}
int main() {
#ifdef debug
freopen("1879.in", "r", stdin);
#endif
for (int kase = 1; ; ++kase) {
scanf("%hd%hd%hd", &n, &m, &l);
swd = (1 << ((l - 1) << 1)) - 1;
if (n == 0 && m == 0 && l == 0) break;
main1(kase);
}
}
测试数据 #8: TimeLimitExceeded, time = 2012 ms, mem = 9048 KiB, score = 0