zoj_ac.rar_zoj_zoj 1023_zoj 2792_zoj21_zoj2182

#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 );