Source code for submission s992

Go to diff to previous submission

fp_pre.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17.  
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25. const int INF = 1<<29;
  26.  
  27. typedef long long ll;
  28.  
  29. struct Tile{
  30. 	char arr[5][5];
  31. };
  32.  
  33. struct Bigtile{
  34. 	char arr[15][15];
  35. };
  36.  
  37. Tile tiles[12][8];
  38.  
  39. char help[28];
  40.  
  41. Tile reflect(const Tile& A){
  42. 	Tile B;
  43. 	REP(i,5) REP(j,5) B.arr[4-i][j] = A.arr[i][j];
  44. 	return B;
  45. }
  46.  
  47. Tile rotate(const Tile& A){
  48. 	Tile B;
  49. 	REP(i,5) REP(j,5) B.arr[4-j][i] = A.arr[i][j];
  50. 	return B;
  51. }
  52.  
  53. Bigtile reflect(const Bigtile& A){
  54. 	Bigtile B;
  55. 	REP(i,15) REP(j,15) B.arr[14-i][j] = A.arr[i][j];
  56. 	return B;
  57. }
  58.  
  59. Bigtile rotate(const Bigtile& A){
  60. 	Bigtile B;
  61. 	REP(i,15) REP(j,15) B.arr[14-j][i] = A.arr[i][j];
  62. 	return B;
  63. }
  64.  
  65. int charnum(char c){
  66. 	if(c=='F') return 0;
  67. 	if(c=='I') return 1;
  68. 	if(c=='L') return 2;
  69. 	if(c=='N') return 3;
  70. 	if(c=='P') return 4;
  71. 	if(c=='T') return 5;
  72. 	if(c=='U') return 6;
  73. 	if(c=='V') return 7;
  74. 	if(c=='W') return 8;
  75. 	if(c=='X') return 9;
  76. 	if(c=='Y') return 10;
  77. 	if(c=='Z') return 11; 
  78. 	return 0;
  79. }
  80.  
  81. Bigtile zero, Xzero,X;
  82. Bigtile shift(const Bigtile& A){
  83. 	Bigtile C = zero;
  84. 	int minX=20, minY=20;
  85. 	REP(i,15)REP(j,15){
  86. 		if (A.arr[i][j] == 'x') {
  87. 			if (i < minY) minY = i;
  88. 			if (j < minX) minX = j;
  89. 		}
  90. 	}
  91. 	if (minX == 20) return A;
  92. 	REP(i,15-minY)REP(j,15-minX){
  93. 		C.arr[i][j] = A.arr[i+minY][j+minX];
  94. 	}
  95. 	return C;
  96. }
  97.  
  98. bool compare(const Bigtile& A, const Bigtile& B){
  99. 	REP(i,15) REP(j,15){
  100. 		if(A.arr[i][j]!=B.arr[i][j]) return false;
  101. 		}
  102. 	return true;
  103. }
  104.  
  105. Bigtile con;
  106.  
  107. void dfs(int x, int y){
  108. 	if(x<0 || y<0 || x>=15 || y>=15) return;
  109. 	if(con.arr[x][y]=='.') return;
  110. 	con.arr[x][y]='.';
  111. 	dfs(x+1,y);
  112. 	dfs(x-1,y);
  113. 	dfs(x,y+1);
  114. 	dfs(x,y-1);
  115. }
  116. bool is_connected(){
  117. 	REP(i,15) REP(j,15){
  118. 		if(con.arr[i][j]=='x'){
  119. 			dfs(i,j);
  120. 			REP(k,15) REP(l,15) if(con.arr[k][l]=='x') return false;
  121. 			return true;
  122. 		}
  123. 	}
  124. 	return true;
  125. }
  126.  
  127.  
  128. vector< Bigtile > pos[12][12];
  129.  
  130. char c1,c2,c3,c4,c5,c6;
  131. bool done[12][12];
  132. int d1,d2,d3,d4;
  133. bool ok;
  134.  
  135. int main() {
  136. 	strcpy(help,".xx..xx....x.............");
  137. 	REP(i,5) REP(j,5) tiles[0][0].arr[i][j] = help[i*5+j];
  138.  
  139. 	strcpy(help,"x....x....x....x....x....");
  140. 	REP(i,5) REP(j,5) tiles[1][0].arr[i][j] = help[i*5+j];
  141.  
  142. 	strcpy(help,"x....x....x....xx........");
  143. 	REP(i,5) REP(j,5) tiles[2][0].arr[i][j] = help[i*5+j];
  144.  
  145. 	strcpy(help,".x....x...xx...x.........");
  146. 	REP(i,5) REP(j,5) tiles[3][0].arr[i][j] = help[i*5+j];
  147.  
  148. 	strcpy(help,"xx...xx...x..............");
  149. 	REP(i,5) REP(j,5) tiles[4][0].arr[i][j] = help[i*5+j];
  150.  
  151. 	strcpy(help,"xxx...x....x.............");
  152. 	REP(i,5) REP(j,5) tiles[5][0].arr[i][j] = help[i*5+j];
  153.  
  154. 	strcpy(help,"x.x..xxx.................");
  155. 	REP(i,5) REP(j,5) tiles[6][0].arr[i][j] = help[i*5+j];
  156.  
  157. 	strcpy(help,"x....x....xxx............");
  158. 	REP(i,5) REP(j,5) tiles[7][0].arr[i][j] = help[i*5+j];
  159.  
  160. 	strcpy(help,"x....xx....xx............");
  161. 	REP(i,5) REP(j,5) tiles[8][0].arr[i][j] = help[i*5+j];
  162.  
  163. 	strcpy(help,".x...xxx...x.............");
  164. 	REP(i,5) REP(j,5) tiles[9][0].arr[i][j] = help[i*5+j];
  165.  
  166. 	strcpy(help,".x...xx....x....x........");
  167. 	REP(i,5) REP(j,5) tiles[10][0].arr[i][j] = help[i*5+j];
  168.  
  169. 	strcpy(help,"xx....x....xx............");
  170. 	REP(i,5) REP(j,5) tiles[11][0].arr[i][j] = help[i*5+j];
  171.  
  172. 	REP(i,12){
  173. 		tiles[i][1] = reflect(tiles[i][0]);
  174. 		REP(j,3){
  175. 			tiles[i][2*j+2] = rotate(tiles[i][2*j]);
  176. 			tiles[i][2*j+3] = rotate(tiles[i][2*j+1]);
  177. 		}
  178. 	}
  179.  
  180. 	REP(i,15) REP(j,15) zero.arr[i][j]='.';
  181. 	while(scanf("%c%c %c%c\n",&c1,&c2,&c3,&c4) == 4){
  182. 		//DEBUG(c1);
  183. 		d1 = charnum(c1);
  184. 		d2 = charnum(c2);
  185. 		d3 = charnum(c3);
  186. 		d4 = charnum(c4);
  187. 		//DEBUG(d1);
  188. 		//DEBUG(d2);
  189. 		//DEBUG(d3);
  190. 		//DEBUG(d4);
  191. 		if(!done[d1][d2]){
  192. 			Xzero = zero;
  193. 			REP(k,8){
  194. 				REP(i,5) REP(j,5) Xzero.arr[i+5][j+5] = tiles[d1][k].arr[i][j];
  195. 				REP(m,10) REP(n,10){
  196. 					ok=true;
  197. 					X = Xzero;
  198. 					REP(i,5) REP(j,5){
  199. 						if(X.arr[i+m][j+n]=='x' && tiles[d2][0].arr[i][j]=='x') ok=false;
  200. 						if(tiles[d2][0].arr[i][j]=='x') X.arr[i+m][j+n]=tiles[d2][0].arr[i][j];
  201. 					}
  202. 					con = X;
  203. 					if(ok && is_connected()){
  204. 						REP(rot,4){
  205. 							pos[d1][d2].push_back(shift(X));
  206. 							pos[d1][d2].push_back(shift(reflect(X)));
  207. 							X = rotate(X);
  208. 						}
  209. 					}
  210. 				}
  211. 			}
  212.  
  213. 		}
  214. 		REP(i,(int)pos[d1][d2].size()) {
  215. 			FOR(j,i+1,(int)pos[d1][d2].size()-1) {
  216. 				if (compare(pos[d1][d2][i], pos[d1][d2][j])) {
  217. 					pos[d1][d2][j] = pos[d1][d2][pos[d1][d2].size()-1];
  218. 					pos[d1][d2].pop_back();
  219. 					--j;
  220. 				}
  221. 			}
  222. 		}
  223.  
  224. 		if(!done[d3][d4]){
  225. 			d1 = d3; d2 = d4;
  226. 			Xzero = zero;
  227. 			REP(k,8){
  228. 				REP(i,5) REP(j,5) Xzero.arr[i+5][j+5] = tiles[d1][k].arr[i][j];
  229. 				REP(m,10) REP(n,10){
  230. 					ok=true;
  231. 					X = Xzero;
  232. 					REP(i,5) REP(j,5){
  233. 						if(X.arr[i+m][j+n]=='x' && tiles[d2][0].arr[i][j]=='x') ok=false;
  234. 						if(tiles[d2][0].arr[i][j]=='x') X.arr[i+m][j+n]=tiles[d2][0].arr[i][j];
  235. 					}
  236. 					con = X;
  237. 					if(ok && is_connected()){
  238. 						REP(rot,4){
  239. 							pos[d1][d2].push_back(shift(X));
  240. 							pos[d1][d2].push_back(shift(reflect(X)));
  241. 							X = rotate(X);
  242. 						}
  243. 					}
  244. 				}
  245. 			}
  246. 		}
  247. 		REP(i,(int)pos[d1][d2].size()) {
  248. 			FOR(j,i+1,(int)pos[d1][d2].size()-1) {
  249. 				if (compare(pos[d1][d2][i], pos[d1][d2][j])) {
  250. 					pos[d1][d2][j] = pos[d1][d2][pos[d1][d2].size()-1];
  251. 					pos[d1][d2].pop_back();
  252. 					--j;
  253. 				}
  254. 			}
  255. 		}
  256. 		d1 = charnum(c1); d2 = charnum(c2);
  257.  
  258. 		ok=false;
  259. 		REP(i,pos[d1][d2].size()){
  260. 			if(ok) break;
  261. 			REP(j,pos[d3][d4].size()){
  262. 				if(ok) break;
  263. 				if(compare(pos[d1][d2][i],pos[d3][d4][j])) ok=true;
  264. 			}
  265. 		}
  266.  
  267. 		printf("%s\n", ok ? "YES" : "NO");
  268. 	}
  269.  
  270. 	return 0;
  271. }
  272.  

Diff to submission s967

fp_pre.cpp

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