题解 P1312 【Mayan游戏】

其实是一道纯暴力搜索+剪枝，暴力枚举每一个点左移还是右移，并对每一次移动暴力模拟掉落和消掉的情况即可。 要注意，在搜索是应该先搜右移，因为【i，j】右移比【i+1，j】左移的字典序要小。所以在剪枝时，如果【i，j】左边不为空，就可以不走，因为之前右移已经剪过了。 还有就是移动时颜色相同可以不用搜，如果一个颜色的块数小于3且不为0，此时不可能全部消完也可以剪掉。偷懒并没有写这个剪枝，前两个已经够了，那么下面是代码 ```cpp #include<cstdio> #include<cstring> #include<iostream> using namespace std; int n; int a[10][10]; int re[10][10]; void fall() { for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) { if(!a[i][j]) continue; int k=j; while(a[i][k-1]==0 && k>1) k--; swap(a[i][j],a[i][k]); } } void print(int x) { for(int i=1;i<=x;i++) cout<<re[i][1]-1<<" "<<re[i][2]-1<<" "<<re[i][3]<<endl; } bool clear() { bool e[10][10]; memset(e,0,sizeof(e)); for(int i=1;i<=3;i++) for(int j=1;j<=7;j++) if(a[i][j]!=0 && a[i][j]==a[i+1][j] && a[i+1][j]==a[i+2][j]) e[i][j]=e[i+1][j]=e[i+2][j]=1; for(int i=1;i<=5;i++) for(int j=1;j<6;j++) if(a[i][j]!=0 && a[i][j]==a[i][j+1] && a[i][j+1]==a[i][j+2]) e[i][j]=e[i][j+1]=e[i][j+2]=1; int k=0; for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) if(e[i][j]) a[i][j]=0,k=1; return k; } bool ok() { for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) if(a[i][j]) return 0; return 1; } bool dfs(int x) { if(ok()) { print(x-1);//注意x要-1 return 1; } if(x>n) return 0; int tmp[10][10]; memcpy(tmp,a,sizeof(tmp)); for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) { if(!a[i][j]) continue; if(i<5 && a[i][j]!=a[i+1][j])//剪枝1 { swap(a[i][j],a[i+1][j]); fall(); while(clear()) fall();//暴力循环处理掉落和消掉 re[x][1]=i,re[x][2]=j,re[x][3]=1; if(dfs(x+1)) return 1; memcpy(a,tmp,sizeof(a)); } if(i>1 && a[i-1][j]==0)//剪枝2 { swap(a[i][j],a[i-1][j]); fall(); while(clear()) fall(); re[x][1]=i,re[x][2]=j,re[x][3]=-1; if(dfs(x+1)) return 1; memcpy(a,tmp,sizeof(a)); } } return 0; } int main() { scanf("%d",&n); for(int i=1;i<=5;i++) { int x,cnt=0; while(++cnt) { scanf("%d",&x); if(x==0) break; a[i][cnt]=x; } } if(!dfs(1)) printf("-1"); return 0; } ```