Go to diff to previous submission
#include <algorithm> #include <cctype> #include <cmath> #include <complex> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> using namespace std; #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl; #define REP(i,a) for (int i = 0; i < (a); ++i) #define FOR(i,a,b) for (int i = (a); i <= (b); ++i) #define FORD(i,a,b) for (int i = (a); i >= (b); --i) inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; } const int INF = 1<<29; typedef long long ll; struct Tile{ char arr[5][5]; }; struct Bigtile{ char arr[15][15]; }; Tile tiles[12][8]; char help[28]; Tile reflect(const Tile& A){ Tile B; REP(i,5) REP(j,5) B.arr[4-i][j] = A.arr[i][j]; return B; } Tile rotate(const Tile& A){ Tile B; REP(i,5) REP(j,5) B.arr[4-j][i] = A.arr[i][j]; return B; } Bigtile reflect(const Bigtile& A){ Bigtile B; REP(i,15) REP(j,15) B.arr[14-i][j] = A.arr[i][j]; return B; } Bigtile rotate(const Bigtile& A){ Bigtile B; REP(i,15) REP(j,15) B.arr[14-j][i] = A.arr[i][j]; return B; } int charnum(char c){ if(c=='F') return 0; if(c=='I') return 1; if(c=='L') return 2; if(c=='N') return 3; if(c=='P') return 4; if(c=='T') return 5; if(c=='U') return 6; if(c=='V') return 7; if(c=='W') return 8; if(c=='X') return 9; if(c=='Y') return 10; if(c=='Z') return 11; return 0; } Bigtile zero, Xzero,X; Bigtile shift(const Bigtile& A){ Bigtile C = zero; int minX=20, minY=20; REP(i,15)REP(j,15){ if (A.arr[i][j] == 'x') { if (i < minY) minY = i; if (j < minX) minX = j; } } if (minX == 20) return A; REP(i,15-minY)REP(j,15-minX){ C.arr[i][j] = A.arr[i+minY][j+minX]; } return C; } bool compare(const Bigtile& A, const Bigtile& B){ REP(i,15) REP(j,15){ if(A.arr[i][j]!=B.arr[i][j]) return false; } return true; } Bigtile con; void dfs(int x, int y){ if(x<0 || y<0 || x>=15 || y>=15) return; if(con.arr[x][y]=='.') return; con.arr[x][y]='.'; dfs(x+1,y); dfs(x-1,y); dfs(x,y+1); dfs(x,y-1); } bool is_connected(){ REP(i,15) REP(j,15){ if(con.arr[i][j]=='x'){ dfs(i,j); REP(k,15) REP(l,15) if(con.arr[k][l]=='x') return false; return true; } } return true; } vector< Bigtile > pos[12][12]; char c1,c2,c3,c4,c5,c6; bool done[12][12]; int d1,d2,d3,d4; bool ok; int main() { strcpy(help,".xx..xx....x............."); REP(i,5) REP(j,5) tiles[0][0].arr[i][j] = help[i*5+j]; strcpy(help,"x....x....x....x....x...."); REP(i,5) REP(j,5) tiles[1][0].arr[i][j] = help[i*5+j]; strcpy(help,"x....x....x....xx........"); REP(i,5) REP(j,5) tiles[2][0].arr[i][j] = help[i*5+j]; strcpy(help,".x....x...xx...x........."); REP(i,5) REP(j,5) tiles[3][0].arr[i][j] = help[i*5+j]; strcpy(help,"xx...xx...x.............."); REP(i,5) REP(j,5) tiles[4][0].arr[i][j] = help[i*5+j]; strcpy(help,"xxx...x....x............."); REP(i,5) REP(j,5) tiles[5][0].arr[i][j] = help[i*5+j]; strcpy(help,"x.x..xxx................."); REP(i,5) REP(j,5) tiles[6][0].arr[i][j] = help[i*5+j]; strcpy(help,"x....x....xxx............"); REP(i,5) REP(j,5) tiles[7][0].arr[i][j] = help[i*5+j]; strcpy(help,"x....xx....xx............"); REP(i,5) REP(j,5) tiles[8][0].arr[i][j] = help[i*5+j]; strcpy(help,".x...xxx...x............."); REP(i,5) REP(j,5) tiles[9][0].arr[i][j] = help[i*5+j]; strcpy(help,".x...xx....x....x........"); REP(i,5) REP(j,5) tiles[10][0].arr[i][j] = help[i*5+j]; strcpy(help,"xx....x....xx............"); REP(i,5) REP(j,5) tiles[11][0].arr[i][j] = help[i*5+j]; REP(i,12){ tiles[i][1] = reflect(tiles[i][0]); REP(j,3){ tiles[i][2*j+2] = rotate(tiles[i][2*j]); tiles[i][2*j+3] = rotate(tiles[i][2*j+1]); } } REP(i,15) REP(j,15) zero.arr[i][j]='.'; while(scanf("%c%c %c%c\n",&c1,&c2,&c3,&c4) == 4){ //DEBUG(c1); d1 = charnum(c1); d2 = charnum(c2); d3 = charnum(c3); d4 = charnum(c4); //DEBUG(d1); //DEBUG(d2); //DEBUG(d3); //DEBUG(d4); if(!done[d1][d2]){ Xzero = zero; REP(k,8){ REP(i,5) REP(j,5) Xzero.arr[i+5][j+5] = tiles[d1][k].arr[i][j]; REP(m,10) REP(n,10){ ok=true; X = Xzero; REP(i,5) REP(j,5){ if(X.arr[i+m][j+n]=='x' && tiles[d2][0].arr[i][j]=='x') ok=false; if(tiles[d2][0].arr[i][j]=='x') X.arr[i+m][j+n]=tiles[d2][0].arr[i][j]; } con = X; if(ok && is_connected()){ REP(rot,4){ pos[d1][d2].push_back(shift(X)); pos[d1][d2].push_back(shift(reflect(X))); X = rotate(X); } } } } } REP(i,(int)pos[d1][d2].size()) { FOR(j,i+1,(int)pos[d1][d2].size()-1) { if (compare(pos[d1][d2][i], pos[d1][d2][j])) { pos[d1][d2][j] = pos[d1][d2][pos[d1][d2].size()-1]; pos[d1][d2].pop_back(); --j; } } } if(!done[d3][d4]){ d1 = d3; d2 = d4; Xzero = zero; REP(k,8){ REP(i,5) REP(j,5) Xzero.arr[i+5][j+5] = tiles[d1][k].arr[i][j]; REP(m,10) REP(n,10){ ok=true; X = Xzero; REP(i,5) REP(j,5){ if(X.arr[i+m][j+n]=='x' && tiles[d2][0].arr[i][j]=='x') ok=false; if(tiles[d2][0].arr[i][j]=='x') X.arr[i+m][j+n]=tiles[d2][0].arr[i][j]; } con = X; if(ok && is_connected()){ REP(rot,4){ pos[d1][d2].push_back(shift(X)); pos[d1][d2].push_back(shift(reflect(X))); X = rotate(X); } } } } } REP(i,(int)pos[d1][d2].size()) { FOR(j,i+1,(int)pos[d1][d2].size()-1) { if (compare(pos[d1][d2][i], pos[d1][d2][j])) { pos[d1][d2][j] = pos[d1][d2][pos[d1][d2].size()-1]; pos[d1][d2].pop_back(); --j; } } } d1 = charnum(c1); d2 = charnum(c2); ok=false; REP(i,pos[d1][d2].size()){ if(ok) break; REP(j,pos[d3][d4].size()){ if(ok) break; if(compare(pos[d1][d2][i],pos[d3][d4][j])) ok=true; } } printf("%s\n", ok ? "YES" : "NO"); } return 0; }
--- c5.s967.cteam010.fp.cpp.0.fp_pre.cpp +++ c5.s992.cteam010.fp.cpp.0.fp_pre.cpp @@ -179,5 +179,5 @@ REP(i,15) REP(j,15) zero.arr[i][j]='.'; - while(scanf("%c%c%c%c%c%c",&c1,&c2,&c5,&c3,&c4,&c6) == 6){ + while(scanf("%c%c %c%c\n",&c1,&c2,&c3,&c4) == 4){ //DEBUG(c1); d1 = charnum(c1); @@ -205,5 +205,5 @@ pos[d1][d2].push_back(shift(X)); pos[d1][d2].push_back(shift(reflect(X))); - rotate(X); + X = rotate(X); } } @@ -239,5 +239,5 @@ pos[d1][d2].push_back(shift(X)); pos[d1][d2].push_back(shift(reflect(X))); - rotate(X); + X = rotate(X); } }