记录编号 | 442677 | 评测结果 | AAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [NOIP 2011]玛雅游戏 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 2.838 s | ||
提交时间 | 2017-08-28 08:46:40 | 内存使用 | 0.31 MiB | ||
#include<bits/stdc++.h>/*注意: a) 如果同时有多组方块满足消除条件,几组方块会同时被消除(例如下面图4,三个颜色为1 的方块和三个颜色为2 的方块会同时被消除 ,最后剩下一个颜色为2 的方块)。 b) 当出现行和列都满足消除条件且行列共享某个方块时,行和列上满足消除条件的所有方块会 被同时消除(例如下面图5 所示的情形,5 个方块会同时被消除)。 任一时刻,如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块,则它们将立即被消除(参见图1 到图3)。*/ using namespace std; int n; struct pic{ int a[10][10],num[11],boo[10][10]; void read(){ memset(a,0,sizeof(a)); for(int i=1;i<=5;i++){ int o=0; int x; while(scanf("%d",&x)){ if(!x)break; a[i][++o]=x; } } } void get(pic b){ memset(a,0,sizeof(a)); for(int i=1;i<=5;i++){ for(int j=1;j<=7;j++) a[i][j]=b.a[i][j]; } } void fall(){ for(int i=1;i<=5;i++){ for(int j=2;j<=7;j++){ int o=j; while(a[i][o]&&!a[i][o-1]&&o-1>0){ a[i][o-1]=a[i][o]; a[i][o]=0; o--; } } } } bool judge(){ for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) if(a[i][j])return 0; return 1; } bool xiao(){ memset(num,0,sizeof(num)); memset(boo,0,sizeof(boo)); int book=0; for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) num[a[i][j]]++; for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ if(!a[i][j])continue; if(num[a[i][j]]<3)continue; int o1=j-1,o2=j+1,o3=i-1,o4=i+1; while(a[i][o1]==a[i][j])o1--; while(a[i][o2]==a[i][j])o2++; while(a[o3][j]==a[i][j])o3--; while(a[o4][j]==a[i][j])o4++; if(o2-o1>3){ for(int k=o1+1;k<o2;k++){ boo[i][k]=1; } book=1; } if(o4-o3>3){//开始没看清题目啊!!!应该给被消的打上标记最后一起消,不然先消的话会造成有些有共用块的没法消了 for(int k=o3+1;k<o4;k++){//还有竖着两个横着三个竖着的那个是不会消的 boo[k][j]=1; } book=1; } } } for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) if(boo[i][j])a[i][j]=0; return book; } }; struct step{ int x,y,to; step(){} step(int a,int b,int c){ x=a; y=b; to=c; } }; int turkey; stack<step>S; stack<step>S2; void dfs(pic a,int t){ if(t>n)return ; if(turkey) return ; if(t==n){ /* for(int i=1;i<=5;i++){ for(int j=1;j<=7;j++) cout<<a.a[i][j]<<" "; cout<<endl; } system("pause");*/ if(a.judge()){ while(!S.empty()){ step u=S.top(); S.pop(); S2.push(u); } while(!S2.empty()){ step u=S2.top(); S2.pop(); cout<<u.x-1<<" "<<u.y-1<<" "<<u.to<<endl; } turkey=1; } else return ; } for(int i=1;i<=5;i++){ for(int j=1;j<=7;j++){ if(!a.a[i][j])continue; if(i+1<=5){ pic m; m.get(a); swap(m.a[i][j],m.a[i+1][j]); m.fall(); while(m.xiao()){ m.fall(); } step p(i,j,1); S.push(p); dfs(m,t+1); if(!S.empty())//一定要加!!!不然找到结果之后S已经空了,再pop就出事了 S.pop(); } if(i-1>=1&&!a.a[i-1][j]){ pic m; m.get(a); swap(m.a[i][j],m.a[i-1][j]); m.fall(); while(m.xiao()){ m.fall(); } step p(i,j,-1); S.push(p); dfs(m,t+1); if(!S.empty()) S.pop(); } } } } int main() { freopen("mayan.in","r",stdin); freopen("mayan.out","w",stdout); // freopen("1.txt","r",stdin); scanf("%d",&n); pic a; a.read(); dfs(a,0); if(!turkey) cout<<-1; return 0; }