p2125.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>

using namespace std;

const int Row		= 9;
const int Col		= 6;
const int Fullmask	= 1073741823;
const int Bitmask	= 7;
const int Bits		= 3;
const int MaxStats	= 43758;
const int MaxHash	= 55533;

const int Shape[5][5] = { { 1, 0 }, { 2, 1+4, 2+8 }, {4, 1+2, 2+4, 4+8, 8+1}, {4, 1+2+4, 2+4+8, 4+8+1, 8+1+2 }, {1, 1+2+4+8} };

const char TTT[6][5] = { "Non", "Sgl", "SgF", "In", "Fir", "Out" };
enum { Non = 0, Sgl, SgF, In, Fir, Out };

void outputSt ( int st )
{
	for( int i = 0; i <= Row; ++ i ) {
		int p = st&Bitmask;
		printf("%s,", TTT[p]);
		st >>= Bits;
	}
	printf("\n");
}

int mask[ Row+1 ];
int hash[ MaxHash ] ;
int data[ MaxStats ], next[ MaxStats ], len ;
int nearby[ MaxStats ][ Row+1 ], match[ MaxStats ][ Row+1 ], ansNum[ MaxStats ];

#define P2(x) (1<<(x))

inline
int GET( int x, int y) {
	return (((x)>>((y)*Bits))&Bitmask);
};

inline
void SET( int& x, int y, int z ) {
	x = ( x & mask[y] ) | ( z << ( Bits * y ) );
};

inline int hcode( int x )
{
	return x % MaxHash ;
}

void initall () 
{
	for( int i = 0; i <= Row; ++ i ) mask[i] = Fullmask^(Bitmask<<(i*3));
	memset ( ansNum, 0, sizeof( ansNum ) );
	memset ( nearby, 0xff, sizeof( nearby ) );
	memset ( match, 0xff, sizeof( match ) );
	memset ( hash, 0xff, sizeof( hash ) ) ;
	len = 0;
}

void addhash ( int x )
{
	int cd = hcode(x);
	data[ len ] = x, next[ len ] = hash[ cd ], hash[ cd ] = len ;
	
	int i, j, k, a, b, l, rec, tot;
	for( i = 0; i <= Row; ++ i ) {
		a = GET(x,i);
		if( a == SgF ) ansNum[len] = 1;
		if( a == In || a == Fir ) { // generate array nearby[], match[]
			tot = 2;
			for( rec = -1, l = 1, j = i+1; j <= Row && l; ++ j ) {
				if( l == 1 && GET(x,j) == Sgl ) {
					tot ++ ; 
					rec = j;
					if( nearby[len][i] == -1 ) nearby[len][i] = j;
				} else
				if( GET(x,j) == In ) ++ l; else
				if( GET(x,j) == Out ) -- l;
			} -- j;
			nearby[len][j] = rec;
			match[len][i] = j, match[len][j] = i;
			if( a == Fir ) ansNum[len] = tot;
		}
	}
	len ++ ;
}

int findhash ( int x )
{
	int cd = hcode(x);
	for( int i = hash[cd]; i != -1; i = next[i] ) if( data[i] == x ) return i;
	return -1;
}

void genStats ( int dep = 0, bool fire = 0, int bk = 0, int st = 0 )
{
	if( dep > Row ) {
		if( fire == 1 && bk == 0 ) 
			addhash ( st );
		return ;
	}
	genStats ( dep + 1, fire, bk, ( st << Bits ) + Non );
	genStats ( dep + 1, fire, bk + 1, ( st << Bits ) + Out );
	if( bk ) {
		genStats ( dep + 1, fire, bk, ( st << Bits ) + Sgl );
		genStats ( dep + 1, fire, bk - 1, ( st << Bits ) + In );
		if( bk == 1 && !fire ) 
			genStats ( dep + 1, 1, bk - 1, ( st << Bits ) + Fir );
	}
	if( bk == 0 && !fire ) genStats ( dep + 1, 1, bk, ( st << Bits ) + SgF );
}

int P;
char mp[Row][Col+5];

void readr ()
{
	int i, j;
	P = 10-P;
	for( i = Row-1; i >= 0; -- i ) scanf("%s", mp[i]);
	for( i = 0; i < Row; ++ i ) for( j = 0; j < Col; ++ j )
		switch( mp[i][j] ) {
			case '.' : mp[i][j] = 0; break;
			case '-' : mp[i][j] = 1; break;
			case 'L' : mp[i][j] = 2; break;
			case 'T' : mp[i][j] = 3; break;
			case '+' : mp[i][j] = 4; break;
		}
}

int Pnt[2][MaxStats], Q[2][MaxStats], sgn, tail;
bool mk[MaxStats];

void Block( int& st, int inv, int ps, int ost = -1 )
{
	if( inv == -1 ) {
		while(1);
		printf("error, inv = -1, statement is %d\n", st); 
		if( ost == -1 ) printf("No ost input\n"); else outputSt( ost );
		outputSt( st );
	}	
	int d = GET(st,ps);
	if( d == Non ) return ;
	switch ( d ) {
		case In :
		case Fir :
		case Out :
			if( nearby[inv][ps] == -1 ) SET(st,match[inv][ps],(d==Fir||GET(st,match[inv][ps])==Fir)?SgF:Non); else SET(st,nearby[inv][ps],d);
		default : 
			SET(st,ps,Non);
	}
}

int Connect( int& st, int inv, int ps ) // Connect ps & ps+1 using open tunnel
{
	int a = GET(st,ps), b = GET(st,ps+1);
	if( a == Non || b == Non ) {
		return a == Non ? b : a;
	} else
	if( a == SgF ) // b must be In
	{
		if( b != In ) while(1);
		return Fir;
	} else
	if( b == SgF ) // a must be Out
	{
		if( a != Out ) while(1);
		SET(st,match[inv][ps],Fir);
		return Out;
	} else
	if( a == Sgl && b == Out ) return Out; else
	if( ( a == Fir || a == In ) && b == Sgl ) return a; else
	if( a == Out && b == Sgl || a == Sgl && b == In )
	{
		SET(st,match[inv][a==Sgl?ps+1:ps],Sgl);
		return Sgl;
	} else
	if( a == Sgl || b == Sgl ) {
		return Sgl;
	} else
	if( b == Fir ) // a must be Out
	{
		if( a != Out ) while(1);
		SET( st, match[inv][ps], Fir ) ;
		return Sgl;
		
	} else
	if( a == In && b == In || a == Out && b == Out )
	{
		SET( st, match[inv][a==In?ps+1:ps], Sgl ) ;
		return a;
	} else
	{ // ab == FirOut || ab == () || ab == )(
		return a == Fir ? SgF : ( a == Out ? Sgl : Non );
	}
}

void CloseCon( int& st, int inv, int ps ) // Connect ps & ps+1 using closed tunnel
{
	int a = GET(st,ps), b = GET(st,ps+1);
	if( a == Non || b == Non ) {
		Block( st, inv, ps ); Block( st, inv, ps+1 );
	} else
	if( a == SgF ) // b must be In
	{
		if( b != In ) while(1);
		SET( st, ps+1, Fir ); SET( st, ps, Non ); Block( st, findhash(st), ps+1 );
	} else
	if( b == SgF ) // a must be Out
	{
		if( a != Out ) while(1);
		SET( st, match[inv][ps], Fir ); SET( st, ps+1, Non ); Block( st, findhash(st), ps );
	} else
	if( a == Sgl && b == Sgl ) {
		SET( st, ps, Non ) ; SET( st, ps+1, Non );
	} else
	if( (a == Sgl && b == In) || (a==Out && b==Sgl) )
	{
		SET( st, match[inv][a==Sgl?ps+1:ps], Sgl );
		SET( st, ps, Non );
		SET( st, ps+1, Non );
	} else
	if( a == Sgl ) // b must be Out
	{
		if( b != Out ) while(1);
		SET( st, ps, Non ); Block( st, findhash(st), ps+1 );
	} else
	if( b == Sgl ) // a must be In | Fir
	{
		if( a != In && a != Fir ) while(1);
		SET( st, ps+1, Non ); Block( st, findhash(st), ps );
	} else
	if( b == Fir ) // a must be Out
	{
		if( a != Out ) while(1);
		SET( st, match[inv][ps], Fir ) ; SET( st, ps, Non ); SET( st, ps+1, Non );
	} else
	if( a == In && b == In || a == Out && b == Out )
	{
		SET( st, match[inv][a==In?ps+1:ps], Sgl ) ;
		if( a == In ) SET( st, ps, In ), SET( st, ps+1, Non ), Block( st, findhash( st ), ps ) ; else
					SET( st, ps, Non ), SET( st, ps+1, Out ), Block( st, findhash(st), ps+1 );
	} else
	{
		SET( st, ps, Non ); SET( st, ps+1, Non );
	}
}

void update( const int& st, const int& ost )
{
	int p = findhash( st ) ;
	if( p == -1 ) return ;
	if( mk[p] ) return ; mk[p] = 1;
	Pnt[sgn][tail] = ost;
	Q[sgn][tail++] = p;
}

void solvr ()
{
	int i, j, k, cur, inv, L, sp, st, ret, qt; sgn = 0;
	Q[sgn][0] = findhash(SgF << ( 3 * P ));  tail = 1;
	int sx = 10, sy = 8, stop = 0;
	for( i = 0; i < Col && !stop; ++ i )
		for( j = 0; j < Row && !stop; ++ j ) 
		{
			if( i == sx && j == sy ) stop = 1;
	//		printf("(%d,%d)=%d\n", i,j,tail);
			sp = mp[j][i]; memset( mk, 0, sizeof( mk ) ); sgn = 1-sgn;
			for( L = tail, tail = cur = 0; cur < L; ++ cur ) 
			{
				for( k = 1; k <= Shape[sp][0]; ++ k ) {
					inv = Q[1-sgn][cur];
					st = data[ inv ]; 
					if( (Shape[sp][k] & 1) == 0 ) {
						Block( st, inv, j+1 );
						if( st != data[inv] ) inv = findhash(st);
						if( inv == -1 ) continue;
					}
					if( (Shape[sp][k] & 2) == 0 ) {
						Block( st, inv, j ) ;
						if( st != data[inv] ) inv = findhash(st);
						if( inv == -1 ) continue;
					}
					qt = Shape[sp][k] & 12;
					if( qt ) {
						ret = Connect( st, inv, j );
						if( qt == 4 ) SET( st, j, ret ), SET(st,j+1,Non); else
						if( qt == 8 ) SET( st, j+1, ret ), SET(st,j,Non); else
						{
							if( ret == Sgl || ret == In || ret == Fir ) { SET( st, j, ret ); SET( st, j+1, Sgl ); } else
							if( ret == Out ) { SET( st, j, Sgl ); SET( st, j+1, Out ) ; } else
							if( ret == SgF ) { SET( st, j, Fir ); SET( st, j+1, Out ) ; } else
							if( ret == Non ) { SET( st, j, In ); SET( st, j+1, Out ) ; };
						}
					} else CloseCon( st, inv, j );
					if( j == Row-1 ) {
						if( st != data[inv] ) inv = findhash(st);
						if( inv == -1 ) continue;
						Block( st, inv, Row );
						st = (st & (Fullmask>>Bits)) << Bits;
					}
/*					if( stop && data[Q[1-sgn][cur]] == 757862988 ) {
						printf("%d\n",k);
						outputSt(st);
						printf("%d\n",findhash(st));
					}*/
					update( st, data[Q[1-sgn][cur]] );
				}
			}
		}
	
	int ans = 0, state, ost;
	for( cur = 0; cur < tail; ++ cur ) if( ans < ansNum [ Q[sgn][cur] ] ) {
		ans = ansNum [ Q[sgn][cur] ];
		state = data[Q[sgn][cur]];
		ost = Pnt[sgn][cur];
	}
	printf("%d\n",ans);
/*	printf("%d\n",state);
	outputSt(ost);
	outputSt(757862988);
	outputSt(682365516);
	printf("%d\n",data[22721]);*/
}

int main ()
{
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	initall () ;
	genStats () ;
	while( 1 == scanf("%d", &P ) ) {
		readr ();
		solvr ();
	}
	return 0;
}