fc2ブログ



ICPC: Intelligent Congruent Partition of Chocolate

2008.07.10 22:57  ACM/ICPC 2008

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 }


スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ