pku2046.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

/***************************************

	Author:Sempr
	Algorithm:BFS
	Date:2006-07-18

***************************************/
#include <stdio.h>
#include <set>
#include <string>
#include <memory.h>
using namespace std;

typedef struct Tset
{
	char t[4][8];
};

bool operator == (const Tset &a, const Tset &b)
{
	int i, j;
	int *pa, *pb;
	pa = (int *)a.t;
	pb = (int *)b.t;
	for (i = 0; i < 8; i++)
		if (pa[i] != pb[i])
			return false;
	return true;
}

typedef struct Q_node
{
	Tset m;
	char x[4], y[4];
	int move;
} Q_node;

const int SIZE = 100000;
const int MOD = 88199;
Q_node Q[SIZE];
int map[4][8];
int Q_head, Q_tail;
Tset hashTable[SIZE * 2];
Tset tar;
int hashLink[SIZE * 2];
int hashEnd;

// 生成hash值 
int hashCode(const Tset &X)
{
	int ans;
	int i, *p;
	p = (int *)X.t;
	ans = 0;
	for (i = 0; i < 8; i++)
		ans = ans ^ p[i];
	ans %= MOD;
	if (ans <= 0)
		ans += MOD;
	return ans;
}

//将数据插入hashTable 
int InsertToHashTable(const Tset &X)
{
	int code = hashCode(X);
	if (hashLink[code] == -1)
	{
		hashLink[code] = 0;
		hashTable[code] = X;
		return 1;
	}
	if (hashTable[code] == X)
		return 0;
	while (hashLink[code])
	{
		code = hashLink[code];
		if (hashTable[code] == X)
			return 0;
	}
	hashLink[code] = hashEnd;
	code = hashEnd++;
	hashTable[code] = X;
	hashLink[code] = 0;
	return 1;
}

/************

判断状态是否是目标状态和是否有重复
返回-1表示是目标状态
返回0表示状态已经存在
返回1表示状态状态不存在 

************/


int Insert(const Q_node &P)
{
	if (P.m == tar)
		return -1;
	return InsertToHashTable(P.m);
}

void createTar()
{
	int i, j;
	for (i = 0; i < 4; i++)
	{
		tar.t[i][7] = 10;
		for (j = 0; j < 7; j++)
			tar.t[i][j] = i * 10 + j + 11;
	}
}

int Solve()
{
	int i, j, k;
	Q_node *P, *nP;
	int x, y, ans;
	int vtf;
	for (i = 0; i < 4; i++)
		for (j = 1; j < 8; j++)
		    scanf("%d", &map[i][j]);
	memset(hashLink, -1, sizeof(hashLink));
	hashEnd = MOD;
	Q_head = 0;
	Q_tail = 1;
	Q[0].move = 0;
	for (i = 0, k = 0; i < 4; i++)
	{
		map[i][0] = (i + 1) * 10 + 1;
		for (j = 1; j < 8; j++)
		{
			if (map[i][j] % 10 == 1)
			{
				map[i][j] = 10;
				Q[0].x[k] = i;
				Q[0].y[k] = j;
				k++;
			}
			Q[0].m.t[i][j] = map[i][j];
		}
		Q[0].m.t[i][0] = map[i][0];
	}
	if (Insert(Q[0]) == -1)
		return 0;
	while (Q_head < Q_tail)
	{
		P = &Q[Q_head];
		for (k = 0; k < 4; k++)
		{
			nP = &Q[Q_tail];
			x = P->x[k];
			y = P->y[k];
			if (P->m.t[x][y] % 10 == 7)
				continue;
			vtf = P->m.t[x][y - 1] + 1;
			if (vtf % 10 == 1)
				continue;
			memcpy(nP->m.t, P->m.t, sizeof(P->m.t));
			memcpy(nP->x, P->x, sizeof(P->x));
			memcpy(nP->y, P->y, sizeof(P->y));
			nP->move = P->move + 1;
			for (i = 0; i < 4; i++)
			{
				for (j = 0; j < 8; j++)
				{
					if (nP->m.t[i][j] == vtf)
					{
						nP->m.t[i][j] = 10;
						nP->x[k] = i;
						nP->y[k] = j;
						nP->m.t[x][y] = vtf;
						i = 4;
						j = 8;
					}
				}
			}
			ans = Insert(Q[Q_tail]);
			if (ans == -1)
				return nP->move;
			if (ans == 1)
				Q_tail++;
		}
		Q_head++;
	}
	return -1;
}

int main()
{
	int T;
//	freopen("PKU2046.in", "r", stdin);
//	freopen("PKU2046.out", "w", stdout);
	scanf("%d", &T);
	createTar();
	while (T--)
	    printf("%d\n", Solve());
//	printf("%d ms\n", clock());
	return 0;
}