1053.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1053 on 2006-01-17 at 18:21:08 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int C_MAX = 20;
const int R_MAX = 20;
const int S_MAX = 16384*C_MAX*R_MAX;
typedef pair<int, int> pii;

class Point {
public:
	int x, y;
	void make();
	bool legal(int, int) const;
};
void Point::make() {
	scanf("%d %d", &x, &y);
	x--; y--;
}
bool Point::legal(int r, int c) const {
	return (x >= 0 && x < r && y >= 0 && y < c);
}

const Point DIR[] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

bool move[R_MAX][C_MAX];
bool vst[S_MAX];
int r, c, l, lp;
Point dox[8];

inline int dir(const Point&, const Point&);
inline void unhash(int&);
int act(int);

int main()
{
	int m, k, i, t;

	for(t = 1; scanf("%d %d %d", &r, &c, &l) != EOF && r != 0; t++) {
		lp = 2 * l - 2;
		for(i = 0; i < l; i++) {
			dox[i].make();
			if(i != 0) m |= dir(dox[i-1], dox[i]) << (2*i-2);
			else m = (dox[0].x*C_MAX+dox[0].y) << lp;
		}
		memset(move, true, sizeof(move)); memset(vst, false, sizeof(vst));
		scanf("%d", &k);
		for(i = 0; i < k; i++) {
			int a, b;
			scanf("%d %d", &a, &b);
			move[a-1][b-1] = false;
		}
		printf("Case %d: %d\n", t, act(m));
	}
	
	return 0;
}

inline int dir(const Point& h, const Point& t)
{
	if(h.x - t.x == -1) return 0;
	else if(h.y - t.y == -1) return 1;
	else if(h.x - t.x == 1) return 2;
	else return 3;
}
inline void unhash(int& p)
{
	int i;
	dox[0].x = (p >> lp) / 20, dox[0].y = (p >> lp) % 20; 
	p &= (1 << lp) - 1;
	for(i = 1; i < l; i++) {
		int o = (p & (3 << (2*i-2))) >> (2*i-2);
		dox[i].x = dox[i-1].x-DIR[o].x; dox[i].y = dox[i-1].y-DIR[o].y;
	}
}
int act(int bs)
{
	queue<pii> Q;
	Point p;
	while(!Q.empty()) Q.pop();
	Q.push(pii(bs, 0)); vst[bs] = true;
	if(dox[0].x == 0 && dox[0].y == 0) return 0;
	while(!Q.empty()) {
		pii t = Q.front(); Q.pop();
		int i; unhash(t.first);
		for(i = 0; i < l; i++) move[dox[i].x][dox[i].y] = false;
		for(i = 0; i < 4; i++) {
			p.x = dox[0].x+DIR[i].x; p.y = dox[0].y+DIR[i].y;
			if(p.legal(r, c) && move[p.x][p.y]) {
				int m = (((t.first << 2) | i) & ((1<<lp)-1)) 
					| ((p.x*C_MAX+p.y) << lp);
				if(p.x == 0 && p.y == 0) return t.second+1;
				else if(!vst[m]) Q.push(pii(m, t.second+1)), vst[m] = true;
			}
		}
		for(i = 0; i < l; i++) move[dox[i].x][dox[i].y] = true;
	}
	return -1;
}