2227.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2227 on 2006-08-29 at 21:47:44 */ 
#include <cstdio>
#include <cctype>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

typedef long long int64;
typedef pair<int, int> pii;
const int N = 4, CN = 32;

int n, m, id[CN], in;
bool g[N*2][N*2];
map<int64, pii> step;

void move(int64&, int64&, int64&, int64&, int, int, int);
int bfs(queue<int64>&, int, bool);
int getD();
int64 getPS();

int main()
{
	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		memset(g, false, sizeof(g)); memset(id, -1, sizeof(id)); in = 0;
		for(int i = 0; i < m; i++) {
			int k1 = getD(), k2 = getD();
			g[k1][k2] = g[k2][k1] = true;
		}
		queue<int64> Qb, Qe;
		step.clear();
		int64 b = getPS(), e = getPS();
		if(b == e) { printf("0\n"); continue; }
		Qb.push(b); Qe.push(e); step[b] = pii(0, -1); step[e] = pii(-1, 0);
		for(int i = 0, r; true; i++) {
			r = bfs(Qb, i, true);
			if(r != -1) { printf("%d\n", r); break; }
			r = bfs(Qe, i, false);
			if(r != -1) { printf("%d\n", r); break; }
		}
	}
	
	return 0;
}

void move(int64& p1, int64& l1, int64& p2, int64& l2, int d1, int d2, int k)
{
	int64 mo, pp1 = p1;
	if(d1) { mo = p1>>((l1-k)<<2); p1 ^= mo<<((l1-k)<<2); }
	else { p1 >>= k<<2; mo = pp1^(p1<<(k<<2)); }
	if(d1 == d2) {
		int e[CN];
		for(int i = 0; i < k; i++, mo >>= 4) e[i] = mo&15;
		for(int i = 0; i < k; i++) mo |= (int64)e[k-1-i]<<(i<<2);
	}
	if(d2) p2 |= mo<<(l2<<2);
	else p2 = (p2<<(k<<2))|mo;
	l1 -= k; l2 += k;
}
int bfs(queue<int64>& Q, int dn, bool beg)
{
#define getSubE(tp) (beg ? tp.first : tp.second)
#define getObjE(tp) (beg ? tp.second : tp.first)
#define setSubE(e) (beg ? pii(e, -1) : pii(-1, e))
	while(!Q.empty()) {
		int64 p = Q.front();
		pii pe = step.find(p)->second;
		if(getSubE(pe) != dn) return -1;
		Q.pop();
		int64 pk[N] = { 0 }, len[N];
		for(int i = 0, j, k = 0; i < n; i++, k += 4) {
			for(j = 0; true; j += 4, k += 4) {
				int64 t = (p>>k)&15;
				if(t == 15) break;
				pk[i] |= t<<j;
			}
			len[i] = j>>2;
		}
		for(int i = 0; i < 2*n; i++)
			for(int j = 0; j < 2*n; j++) {
				if(!g[i][j]) continue;
				for(int k = 1; k <= len[i>>1]; k++) {
					int64 tk[N], tl[N], st = 0;
					memcpy(tk, pk, sizeof(tk)); memcpy(tl, len, sizeof(tl));
					move(tk[i>>1], tl[i>>1], tk[j>>1], tl[j>>1], i&1, j&1, k);
					for(int x = 0, y = 0; x < n; y += (tl[x]+1)<<2, x++) 
						{ st |= tk[x]<<y; st |= 15LL << (y+tl[x]*4); }
					if(!step.count(st)) { step[st] = setSubE(dn+1); Q.push(st); continue; }
					pii te = step.find(st)->second;
					if(getObjE(te) != -1) return getObjE(te)+dn+1;
				}
			}
	}
	return -1;
}
int getD()
{
	char c; int p;
	scanf("%d%c", &p, &c);
	return (p<<1)|(c=='E');
}
int64 getPS()
{
	int64 st = 0;
	char park[24];
	for(int i = 0, j = 0; i < n; i++, j += 4) {
		scanf("%s", park);
		for(int k = 0; isalpha(park[k]); j += 4, k++) {
			if(id[park[k]-'a'] == -1) id[park[k]-'a'] = in++;
			st |= (int64)id[park[k]-'a'] << j;
		}
		st |= 15LL << j;
	}
	return st;
}