也是一个鬼得不行的搜索题。。
剪剪枝就完了
【代码是我蒯的 真的没力气写这种鬼题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
// <mayan.cpp> - 02/11/16 10:30:45 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } struct T{ int x,y,ops; }ans[10]; int st[10][10]; int n; bool empty(){ for(int i=0;i<5;i++) for(int j=0;j<7;j++) if(st[i][j])return false; return true; } void drop(){ int num[10][10]; memset(num,-1,sizeof num); for(int x=0;x<5;x++){ int h=0; for(int y=0;y<7;y++) if(st[x][y])num[x][h++]=y; } for(int x=0;x<5;x++) for(int y=0;y<7;y++) st[x][y]=num[x][y]==-1?0:st[x][num[x][y]]; return; } bool clear(){ bool flag=0; for(int x=0;x<3;x++) for(int y=0;y<7;y++) if(st[x][y]){ int x2; for(x2=x;x2+1<5&&st[x2+1][y]==st[x][y];x2++); if(x2-x>=2){ int tx; for(tx=x;tx<=x2;tx++){ int Up=y,Dn=y; while(Up+1<7&&st[tx][Up+1]==st[x][y])Up++; while(Dn-1>=0&&st[tx][Dn-1]==st[x][y]) Dn--; if(Up-Dn>=2) for(int ty=Dn;ty<=Up;ty++)st[tx][ty]=0; } for(tx=x;tx<=x2;tx++)st[tx][y]=0; flag=1; } } for(int x=0;x<5;x++) for(int y=0;y<5;y++) if(st[x][y]){ int y2; for(y2=y;y2+1<7&&st[x][y2+1]==st[x][y];y2++); if(y2-y>=2){ for(int ty=y;ty<=y2;ty++){ int Lf=x,Ri=x; while(Lf-1>=0&&st[Lf-1][ty]==st[x][y])Lf--; while(Ri+1<7&&st[Ri+1][ty]==st[x][y])Ri++; if(Ri-Lf>=2) for(int tx=Lf;tx<=Ri;tx++)st[tx][ty]=0; } for(int ty=y;ty<=y2;ty++)st[x][ty]=0; flag=1; } } if(flag)return true; else return false; } void dfs(int step){ if(step>n){ if(empty()){ for(int i=1;i<=n;i++){ if(ans[i].ops)printf("%d %d %d\n",ans[i].x+1,ans[i].y,-1); else printf("%d %d %d\n",ans[i].x,ans[i].y,1); } exit(0); } return; } int sum[12]; memset(sum,0,sizeof sum); for(int x=0;x<5;x++) for(int y=0;y<7;y++) sum[st[x][y]]++; for(int i=1;i<=10;i++) if(sum[i]&&sum[i]<3)return; for(int x=0;x<4;x++) for(int y=0;y<7;y++) if(st[x][y]!=st[x+1][y]){ ans[step].x=x; ans[step].y=y; ans[step].ops=(!st[x][y]); int temp[10][10]; memcpy(temp,st,sizeof temp); swap(st[x][y],st[x+1][y]); drop(); while(clear())drop(); dfs(step+1); ans[step].x=0; ans[step].y=0; ans[step].ops=0; memcpy(st,temp,sizeof st); } } int main(){ freopen("mayan.in","r",stdin); freopen("mayan.out","w",stdout); scanf("%d",&n); for(int i=0;i<5;i++) for(int j=0;;j++){ st[i][j]=getint(); if(!st[i][j])break; } dfs(1); printf("-1\n"); return 0; } |