Guest User

Untitled

a guest
Nov 5th, 2014
230
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define sqr(x) (x)*(x)
  3. #define oo 1000000007
  4. #define pb push_back
  5. #define sz(a) int(a.size())
  6.  
  7. using namespace std;
  8.  
  9. typedef pair<int,int> pii;
  10. typedef long long ll;
  11.  
  12. const int base=73471;
  13. const int dx[4]={-1,0,1,0};
  14. const int dy[4]={0,1,0,-1};
  15.  
  16. map<ll,bool> dp;
  17. int T;
  18. char s[5][7];
  19. pii p[100];
  20. int cnt;
  21.  
  22. bool finish(){
  23. for(int i=0; i<5; ++i) for(int j=0; j<6; ++j) if(s[i][j]!='.') return 0;
  24. return 1;
  25. }
  26.  
  27. ll hash(){
  28. ll res=0;
  29. for(int i=0; i<5; ++i) for(int j=0; j<7; ++j) res=res*base+s[i][j];
  30. return res;
  31. }
  32.  
  33. bool mark[7];
  34.  
  35. void collapse(){
  36. //collapse down
  37. for(int j=0; j<6; ++j){
  38. int last=4;
  39. for(int i=4; i>=0; --i) if(s[i][j]!='.'){
  40. s[last][j]=s[i][j];
  41. if(last!=i) s[i][j]='.';
  42. --last;
  43. }
  44. mark[j]=(last!=4);
  45. }
  46. //shift left
  47. int last=0;
  48. for(int j=0; j<6; ++j) if(mark[j]){
  49. for(int i=0; i<5; ++i) s[i][last]=s[i][j];
  50. ++last;
  51. }
  52. for(;last<6; ++last) for(int i=0; i<5; ++i) s[i][last]='.';
  53. }
  54.  
  55. void dfs(int x, int y, bool mark[5][7]){
  56. ++cnt;
  57. p[cnt]=pii(x,y);
  58. mark[x][y]=0;
  59. int xt,yt;
  60. for(int k=0; k<4; ++k){
  61. xt=x+dx[k]; yt=y+dy[k];
  62. if(xt<0 || yt<0 || xt>4 || yt>5) continue;
  63. if(!mark[xt][yt] || s[xt][yt]!=s[x][y]) continue;
  64. dfs(xt,yt,mark);
  65. }
  66. }
  67.  
  68. bool canComplete;
  69.  
  70. void check(){
  71. if(canComplete) return;
  72. if(finish()){
  73. canComplete=1;
  74. return;
  75. }
  76. ll v=hash();
  77. if(dp.count(v)) return;
  78. dp[v]=1;
  79. char save[5][7];
  80. bool mark[5][7];
  81. for(int i=0; i<5; ++i) for(int j=0; j<6; ++j) save[i][j]=s[i][j], mark[i][j]=1;
  82. bool res=0;
  83. bool didChanged = 0;
  84. for(int i=1; i<5; ++i) for(int j=0; j<6; ++j) if(mark[i][j] && s[i][j]!='.'){
  85. if(didChanged){
  86. //restore
  87. for(int x=0; x<5; ++x) for(int y=0; y<6; ++y) s[x][y]=save[x][y];
  88. didChanged=0;
  89. }
  90. cnt=0;
  91. dfs(i,j,mark);
  92. if(cnt>1){
  93. didChanged=1;
  94. for(int i=1; i<=cnt; ++i) s[p[i].first][p[i].second]='.';
  95. // for(int i=0; i<5; ++i){
  96. // for(int j=0; j<6; ++j) printf("%c",s[i][j]);
  97. // puts("");
  98. // }
  99. // puts("");
  100. collapse();
  101. // for(int i=0; i<5; ++i){
  102. // for(int j=0; j<6; ++j) printf("%c",s[i][j]);
  103. // puts("");
  104. // }
  105. // puts("---------");
  106. // if(s[4][0]=='B' && s[4][1]=='Y'){
  107. // puts("NOW");
  108. // }
  109. check();
  110. }
  111. }
  112. if(didChanged){
  113. //restore
  114. for(int x=0; x<5; ++x) for(int y=0; y<6; ++y) s[x][y]=save[x][y];
  115. didChanged=0;
  116. }
  117. }
  118.  
  119. int main(){
  120. //freopen("input.txt","r",stdin);
  121. scanf("%d",&T);
  122. for(int tt=1; tt<=T; ++tt){
  123. for(int i=0; i<5; ++i) scanf("%s",s[i]);
  124. dp.clear();
  125. canComplete=0;
  126. check();
  127. printf("Case %d: ",tt);
  128. if(canComplete) puts("Yes"); else puts("No");
  129. }
  130. }
RAW Paste Data