Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define sqr(x) (x)*(x)
- #define oo 1000000007
- #define pb push_back
- #define sz(a) int(a.size())
- using namespace std;
- typedef pair<int,int> pii;
- typedef long long ll;
- const int base=73471;
- const int dx[4]={-1,0,1,0};
- const int dy[4]={0,1,0,-1};
- map<ll,bool> dp;
- int T;
- char s[5][7];
- pii p[100];
- int cnt;
- bool finish(){
- for(int i=0; i<5; ++i) for(int j=0; j<6; ++j) if(s[i][j]!='.') return 0;
- return 1;
- }
- ll hash(){
- ll res=0;
- for(int i=0; i<5; ++i) for(int j=0; j<7; ++j) res=res*base+s[i][j];
- return res;
- }
- bool mark[7];
- void collapse(){
- //collapse down
- for(int j=0; j<6; ++j){
- int last=4;
- for(int i=4; i>=0; --i) if(s[i][j]!='.'){
- s[last][j]=s[i][j];
- if(last!=i) s[i][j]='.';
- --last;
- }
- mark[j]=(last!=4);
- }
- //shift left
- int last=0;
- for(int j=0; j<6; ++j) if(mark[j]){
- for(int i=0; i<5; ++i) s[i][last]=s[i][j];
- ++last;
- }
- for(;last<6; ++last) for(int i=0; i<5; ++i) s[i][last]='.';
- }
- void dfs(int x, int y, bool mark[5][7]){
- ++cnt;
- p[cnt]=pii(x,y);
- mark[x][y]=0;
- int xt,yt;
- for(int k=0; k<4; ++k){
- xt=x+dx[k]; yt=y+dy[k];
- if(xt<0 || yt<0 || xt>4 || yt>5) continue;
- if(!mark[xt][yt] || s[xt][yt]!=s[x][y]) continue;
- dfs(xt,yt,mark);
- }
- }
- bool canComplete;
- void check(){
- if(canComplete) return;
- if(finish()){
- canComplete=1;
- return;
- }
- ll v=hash();
- if(dp.count(v)) return;
- dp[v]=1;
- char save[5][7];
- bool mark[5][7];
- for(int i=0; i<5; ++i) for(int j=0; j<6; ++j) save[i][j]=s[i][j], mark[i][j]=1;
- bool res=0;
- bool didChanged = 0;
- for(int i=1; i<5; ++i) for(int j=0; j<6; ++j) if(mark[i][j] && s[i][j]!='.'){
- if(didChanged){
- //restore
- for(int x=0; x<5; ++x) for(int y=0; y<6; ++y) s[x][y]=save[x][y];
- didChanged=0;
- }
- cnt=0;
- dfs(i,j,mark);
- if(cnt>1){
- didChanged=1;
- for(int i=1; i<=cnt; ++i) s[p[i].first][p[i].second]='.';
- // for(int i=0; i<5; ++i){
- // for(int j=0; j<6; ++j) printf("%c",s[i][j]);
- // puts("");
- // }
- // puts("");
- collapse();
- // for(int i=0; i<5; ++i){
- // for(int j=0; j<6; ++j) printf("%c",s[i][j]);
- // puts("");
- // }
- // puts("---------");
- // if(s[4][0]=='B' && s[4][1]=='Y'){
- // puts("NOW");
- // }
- check();
- }
- }
- if(didChanged){
- //restore
- for(int x=0; x<5; ++x) for(int y=0; y<6; ++y) s[x][y]=save[x][y];
- didChanged=0;
- }
- }
- int main(){
- //freopen("input.txt","r",stdin);
- scanf("%d",&T);
- for(int tt=1; tt<=T; ++tt){
- for(int i=0; i<5; ++i) scanf("%s",s[i]);
- dp.clear();
- canComplete=0;
- check();
- printf("Case %d: ",tt);
- if(canComplete) puts("Yes"); else puts("No");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement