1476.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1476 on 2006-07-02 at 10:24:37 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 64;
const int SN = N*N*N;
const int INF = 1 << 28;

char g[N][N];
int n;

int hash(int*);
int move(int*);

int main()
{
	int p[3], i, j;

	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < 3; i++) { scanf("%d", &p[i]); p[i]--; }
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) scanf("\n%c", &g[i][j]);
		int r = move(p);
		if(r == INF) printf("impossible\n");
		else printf("%d\n", r);
	}
	
	return 0;
}

int hash(int* p)
{
	int i, r = 0; sort(p, p+3);
	for(i = 0; i < 3; i++)
		r |= p[i] << (i*6);
	return r;
}
int move(int *b)
{
	if(b[0] == b[1] && b[1] == b[2]) return 0;
	int step[SN], i, j, bs = hash(b);
	memset(step, -1, sizeof(step)); step[bs] = 0;
	queue<int> Q; Q.push(bs);
	while(!Q.empty()) {
		int s = Q.front(), t = s, p[3]; Q.pop();
		for(i = 0; i < 3; i++, t >>= 6) p[i] = t&63;
		for(i = 0; i < 3; i++) {
			int a, b;
			if(i == 0) { a = p[1]; b = p[2]; }
			else { a = p[0]; b = p[3-i]; }
			for(j = 0; j < n; j++)
				if(g[p[i]][j] == g[a][b]) {
					if(a == b && b == j) return step[s]+1;
					int nt[3]; memcpy(nt, p, sizeof(nt)); nt[i] = j;
					int ns = hash(nt);
					if(step[ns] != -1) continue;
					step[ns] = step[s]+1; Q.push(ns);
				}
		}
	}
	return INF;
}