题目：https://www.luogu.org/problemnew/show/P1312
自己写了很久。又T又WA的。
发现对题理解有误。改完后应该只有T了，但还是T的。
自己写了许多剪枝，很鸡肋。
然后去看Zinn的题解。
重要剪枝：交换的话只从左向右即可！！！向左的只能是空格。两个颜色相同的话就不要换了！（虽然可能需要故意浪费步数？）
然后就变得非常快。但WA了1个点。去掉自以为等价的那个地方就能了，而且好像还变快了？不知为何。该处见注释。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=8,K=15; int n,sta[N][5],a[N][N][N],cnt,ct[K],sum,mx; int xx[5]={-1,0,0,1},yy[5]={0,-1,1,0}; bool vis[N][N],eflag; void dfs(int cr,int x,int y,int fx) { cnt++;vis[x][y]=1; int tx=x+xx[fx],ty=y+yy[fx]; if(!vis[tx][ty]&&a[cr][tx][ty]==a[cr][x][y]) dfs(cr,tx,ty,fx); } void cz(int cr,int x,int y) { if(x>1&&a[cr][x-1][y]==a[cr][x][y]&&a[cr][x-2][y]==a[cr][x][y]) dfs(cr,x,y,0); if(y>1&&a[cr][x][y-1]==a[cr][x][y]&&a[cr][x][y-2]==a[cr][x][y]) dfs(cr,x,y,1); //上面两个去掉会错？//去掉上面还会变慢？ if(x<3&&a[cr][x+1][y]==a[cr][x][y]&&a[cr][x+2][y]==a[cr][x][y]) dfs(cr,x,y,3); if(y<5&&a[cr][x][y+1]==a[cr][x][y]&&a[cr][x][y+2]==a[cr][x][y]) dfs(cr,x,y,2); } void xc(int cr) { int tmp[N][N]={0}; for(int i=0;i<=4;i++) { int p0=0; for(int j=0;j<=6;j++) { while(p0<6&&vis[i][p0])p0++; if(vis[i][p0]||!a[cr][i][p0])break; tmp[i][j]=a[cr][i][p0];p0++; } } memcpy(a[cr],tmp,sizeof tmp); } void clear(int cr) { while(1) { memset(vis,0,sizeof vis); cnt=0; for(int i=0;i<=4;i++) for(int j=0;j<=6&&a[cr][i][j];j++) if(!vis[i][j])cz(cr,i,j); if(!cnt)break; xc(cr); sum-=cnt; } } void calc(int cr,int x,int y,int op) { memcpy(a[cr],a[cr-1],sizeof a[cr-1]); if(a[cr][x+op][y]) { if(a[cr][x][y]==a[cr][x+op][y])return; swap(a[cr][x][y],a[cr][x+op][y]); clear(cr); return; } else { for(int i=0;i<=6;i++) if(!a[cr][x+op][i]) {a[cr][x+op][i]=a[cr][x][y];break;} for(int i=y;i<=6;i++)a[cr][x][i]=a[cr][x][i+1]; clear(cr); return; } } bool pan(int cr) { memset(ct,0,sizeof ct); for(int i=0;i<=4;i++) for(int j=0;j<=6&&a[cr][i][j];j++) ct[a[cr][i][j]]++; for(int i=1;i<=mx;i++)if(ct[i]==1||ct[i]==2)return false; return true; } void solve(int cr) { if(cr>n) { eflag=!sum; return; } int ysum=sum; for(int i=0;i<=4;i++) for(int j=0;j<=6&&a[cr-1][i][j];j++) { if(i<4&&a[cr-1][i][j]!=a[cr-1][i+1][j]) { calc(cr,i,j,1); if(pan(cr)) { sta[cr][0]=i;sta[cr][1]=j;sta[cr][2]=1; solve(cr+1); if(eflag)return; } sum=ysum; } if(i>0&&!a[cr-1][i-1][j]) { calc(cr,i,j,-1); if(pan(cr)) { sta[cr][0]=i;sta[cr][1]=j;sta[cr][2]=-1; solve(cr+1); if(eflag)return; } sum=ysum; } } } int main() { scanf("%d",&n); for(int i=0;i<=4;i++) for(int j=0;j<=7;j++)//7 { scanf("%d",&a[0][i][j]); if(!a[0][i][j])break; ct[a[0][i][j]]++; sum++; mx=max(mx,a[0][i][j]); } if(!pan(0)){puts("-1");return 0;} solve(1); if(eflag) { for(int i=1;i<=n;i++) printf("%d %d %d ",sta[i][0],sta[i][1],sta[i][2]); } else puts("-1"); return 0; }