Beyond the Void
BYVoid
USACO 3.2.5 Magic Squares 魔板 msquare
本文正體字版由OpenCC轉換

這道題類似於八數碼難題,基本思想是寬搜,使用Hash判重。如果使用一般的八維數組空間可以達到8^8=16777216,會超過USACO的16MB空間限制。所以我們應該對狀態進行散列存儲,觀察發現每位的數字不能重複,存在空間冗餘。我們可以對於每個狀態建立一個映射,採用康託展開算法。(參見Nocow) 定義cantor(s)爲s串大大小順序。可樣將哈希容量縮減到8!=40320。

另外發現,對於魔板當前狀態可以由一個8位的8進制數來表示,即無符號32位長整型 unsigned long 表示。 對於魔板的變換可以轉化爲對一個數字的位運算。這樣可以大大提高程序效率。

程序有些長,但是效率很高。

USER: CmYkRgB CmYkRgB [cmykrgb1]
TASK: msquare
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 3476 KB]
   Test 2: TEST OK [0.054 secs, 3444 KB]
   Test 3: TEST OK [0.011 secs, 3476 KB]
   Test 4: TEST OK [0.011 secs, 3472 KB]
   Test 5: TEST OK [0.011 secs, 3480 KB]
   Test 6: TEST OK [0.022 secs, 3476 KB]
   Test 7: TEST OK [0.022 secs, 3476 KB]
   Test 8: TEST OK [0.023 secs, 3484 KB]

All tests OK.
/*
ID: cmykrgb1
PROG: msquare
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 40320
using namespace std;

class state
{
public:
	state()
	{
		comefrom=0;cur=0;cont=0;
	}
	state *comefrom;
	unsigned long cur;
	short cont;
};
state O;
state S[MAX];

class queue
{
private:
	long first,last;
	long list[MAX];
public:
	long size;
	
	queue()
	{
		reset();
	}
	
	void reset()
	{
		first=0;
		size=0;
		last=-1;
	}

	void ins(state *comefrom,unsigned long cur,long cont)
	{
		size++;
		last++;
		list[last]=last;
		S[last].comefrom=comefrom;
		S[last].cur=cur;
		S[last].cont=cont;
	}
	
	long del()
	{
		size--;
		return list[first++];
	}
};

ifstream fi("msquare.in");
ofstream fo("msquare.out");
bool hash[MAX];
char B[4]={0,'A','B','C'};

long fac[8]={1,1,2,6,24,120,720,5040};
unsigned long Finish;

unsigned long cantor(unsigned long S)
{
	long x=0,i,p,k,j;
	bool hash[8]={false};
	for (i=8;i>=2;i--)
	{
		k=S>> 3*(i-1);
		S-=k<<3*(i-1);
		hash[k]=true;
		p=k;
		for (j=0;j<=k-1;j++)
			if (hash[j])
				p--;
		x+=fac[i-1]*p;
	}
	return x;
}

void init()
{
	long i,t;
	for (i=0;i<8;i++)
	{
		fi>>t;
		t--;
		O.cur*=8;
		O.cur+=t;
	}
	Finish=cantor(O.cur);
	hash[0]=true;
}

unsigned long turn(unsigned long S,int f)
{
	long i;
	unsigned long P=0;
	switch (f)
	{
	case 1:
		for (i=1;i<=8;i++)
			P+=(S & (7<< ( (i-1)*3) ) )>> (i-1)*3 << ((8-i)*3);
		return P;
		break;
	case 2:
		P+=(S & 07000)>>3*3;
		P+=(S & 00777)<<3;
		P+=(S & 070000)<<3*3;
		P+=(S & 077700000)>>3;
		return P;
		break;
	case 3:
		P= (S & 070077007);
		P+=(S & 070)<<5*3;
		P+=(S & 0700)>>1*3;
		P+=(S & 0700000)>>3*3;
		P+=(S & 07000000)>>1*3;
		return P;
		break;
	}
}

void print(long ed,long f)
{
	string O;
	state *P=&S[ed];
	char OUT[MAX];
	long cnt=0,i;
	while (P->cont)
	{
		cnt++;
		OUT[cnt]=B[P->cont];
		P=P->comefrom;
	}
	
	fo << cnt+1<<endl;
	for (i=cnt;i>=1;i--)
		fo << OUT[i];
	fo << B[f] << endl;

	fi.close();
	fo.close();
	exit(0);
}

void bfs()
{
	long i=0,j;
	queue Q;
	Q.ins(&O,001234567,0);
	while (Q.size)
	{
		unsigned long p,ct;
		i=Q.del();
		for (j=1;j<=3;j++)
		{
			p=turn(S[i].cur,j);
			ct=cantor(p);
			if (!hash[ct])
			{
				hash[ct]=true;
				if (ct==Finish)
					print(i,j);
				Q.ins(&S[i],p,j);
			}
		}
	}
}

int main()
{
	init();
	bfs();
	fo << '0' <<'n'<<'n';
	fi.close();
	fo.close();
	return 0;
}

上次修改時間 2017-02-03

相關日誌