ICPC: Intelligent Congruent Partition of Chocolate

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156

001 #include<iostream>
002 #include<algorithm>
003 #include<set>
004 #include<map>
005 using namespace std;
006 typedef set<int> Shape;
007 #define MAX 12
008 int W, H, C[MAX][MAX], ncell, sx, sy, tx, ty, sd, td, flip;
009 bool V[MAX][MAX];
010 map<Shape, bool> U;
011 
012 void rotate( int &x, int &y ){
013     if ( td == 1 ){ swap( x, y ); x *= (-1);}
014     else if ( td == 2 ) { x *= (-1); y *= (-1);}
015     else if ( td == 3 ) { swap( x, y ); y *= (-1);}
016     x *= flip;
017 }
018 
019 bool dfs( Shape shape ){
020     if ( shape.size() == ncell ) return true;
021     
022     U[shape] = true;
023     
024     static const int dx[4] = {0, -1, 0, 1};
025     static const int dy[4] = {1, 0, -1, 0};
026     int nx, ny, tnx, tny, diffx, diffy;
027     Shape nextS;
028     
029     for ( Shape::iterator it = shape.begin(); it != shape.end(); it++ ){
030         for ( int d = 0; d < 4; d++ ){
031             nx = (*it)/W + dx[d];
032             ny = (*it)%W + dy[d];
033             if ( !C[nx][ny] || V[nx][ny] ) continue;
034             diffx = nx - sx;
035             diffy = ny - sy;
036             rotate( diffx, diffy );
037             tnx = tx + diffx;
038             tny = ty + diffy;
039             if ( nx == tnx && ny == tny ) continue;
040             if ( !C[tnx][tny] || V[tnx][tny] ) continue;
041             nextS = shape;
042             nextS.insert( nx*W + ny );
043             if ( U[nextS] ) continue;
044             V[nx][ny] = V[tnx][tny] = true;
045             if ( dfs( nextS ) ) return true;
046             V[nx][ny] = V[tnx][tny] = false;
047         }
048     }
049     return false;
050 }
051 
052 bool parse(){
053     U = map<Shape, bool>();
054     for ( int x = 1; x <= H; x++ ){
055         for ( int y = 1; y <= W; y++ ) V[x][y] = 0;
056     }
057     Shape shape;
058     shape.insert( sx*W + sy );
059     U[shape] = true;
060     V[sx][sy] = V[tx][ty] = true;
061     return dfs( shape );
062 }
063 
064 bool check(){
065     if ( ncell % 2 != 0 || ncell < 2 ) return false;
066     ncell /= 2;
067     for ( tx = 1; tx <= H; tx++ ){
068         for ( ty = 1; ty <= W; ty++ ){
069             if ( (tx == sx && ty == sy) || C[tx][ty] == 0) continue;
070             for ( td = 0; td < 4; td++ ){
071                 flip = 1;
072                 if ( parse() ) return true;
073                 flip = -1;
074                 if ( parse() ) return true;
075             }
076         }
077     }
078     return false;
079 }
080 
081 main(){
082     while( cin >> W >> H && ( W && H ) ){
083         ncell = 0;
084         sx = sy = -1;
085         for ( int x = 0; x < H + 2; x++ ){
086             for ( int y = 0; y < W + 2; y++ ){
087                 C[x][y] = 0;
088                 if ( 1 <= x && 1 <= y && x <= H && y <= W ) cin >> C[x][y];
089                 if ( C[x][y] ) ncell++;
090                 if ( C[x][y] && sx == -1 ){ sx = x; sy = y; }
091             }
092         }
093         if ( check() ) cout << "YES" << endl;
094         else cout << "NO" << endl;
095     }
096 }