P1312 Mayan游戏（dfs，模拟）

P1312 Mayan游戏

题目大意

太复杂了一点，自己看吧

大概是说一款类似于消消乐的游戏，每次每个方块只能左右移动/交换，当至少有连续三个方块排成一列或者时才能消去，消去之后有可能触发连锁反应.

题目分析

20pts：

有一档“没有解决方案则输出-1”，直接输出-1就有20分了.

30pts：

实际上这一档是40pts，只要处理一排的情况并在不是一排的时候输出-1就行了.

代码实现也很简单，因为没有掉落的情况，而且有效数字只有最多5位，所以要么一排都是同一个数字和0，要么无解.

---

100pts：

观察数据范围，最多操作的次数$n<=5$，妥妥的搜索.

分步设计为现在是第几个操作，状态是现在的操作，状态的转移就是整个游戏矩阵的转移. 设计dfs为bool型，按照优先级搜索如果搜索到结果直接存答案并返回.

现在的操作：

对于每一个当前有方块的点，我们可以对它进行两种操作：左移和右移.

而由题目的“优先级”，向左是劣于向右的，这启示我们，我们只会在左边没有方块的时候左移，因为与其这个方块左移，不如左边的方块右移，而且这两个状态是重复的.

右移就没有条件限制了.

//mp表示当前的游戏界面 for(int i=0;i<5;i++){ for(int j=0;j<7;j++){ //根据题目最优解原则，由优向劣搜索 if(!mp[i][j])continue; //只有有方块的点才能进行操作 if(i<4){//边界处理 swap(mp[i][j],mp[i+1][j]); bool w=dfs(step+1); if(w){ ans[step].l =i,ans[step].r =j; ans[step].op =1; return true; }//记录答案直接返回 swap(mp[i][j],mp[i+1][j]);//回复原状态 }//以上为右移操作 if(i>0&&!mp[i-1][j]){ swap(mp[i-1][j],mp[i][j]); bool w=dfs(step+1); if(w){ ans[step].l =i,ans[step].r =j; ans[step].op =-1; return true; } swap(mp[i-1][j],mp[i][j]); }//以上为左移操作 } }

---

掉落操作：

由于题目规定一个方块不能被架空，所以我们应该把那些架空的方块下放.

for(int i=0;i<5;i++){ int k=-1; for(int j=0;j<7;j++){ if(mp[i][j]){ mp[i][++k]=mp[i][j]; }//下放方块 } for(int j=k+1;j<7;j++){ mp[i][j]=0; }//清空被下放的方块原来的位置 }//drop

---

查找能够被消去的方块：

这是这道题的重点. 因为把所有颜色放在一起不方便看，所以我们不妨一种颜色一种颜色地看.

如果同时有多组方块满足消除条件，几组方块会同时被消除； 当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除； 方块消除之后，消除位置之上的方块将掉落，掉落后可能会引起新的方块消除。注意：掉落的过程中将不会有方块的消除.

for(int k=1;k<=10;k++){//一种颜色一种颜色地看 memset(ck,false,sizeof ck); int tot=0; for(int i=0;i<5;i++){ for(int j=0;j<7;j++){ if(mp[i][j]==k){ ck[i][j]=true; //ck用来存当前图的这种颜色的方块 tot++; } } } if(tot<3&&tot){ for(int i=0;i<5;i++){ for(int j=0;j<7;j++)mp[i][j]=upd[i][j]; }//记得回复原值 return false; }//小优化，如果一种颜色的方块数量不能满足消掉的最小数量（3），直接返回 memset(q,false,sizeof q);//q数组用来存能够消去的位置 for(int i=0;i<5;i++){ for(int j=0;j<7;j++){ if(ck[i][j]){ deal(i,j,1); deal(i,j,2);//deal处理能够消去的方块 //1,2表示是横向还是纵向，每次遇到这个颜色的方块就处理一次，虽然暴力但是能保证正确性 //由于是两个方向同时进行检查的，所以如果出现丁字形的或者L字形的也可以消去 } } } for(int i=0;i<5;i++){ for(int j=0;j<7;j++){ if(q[i][j])mp[i][j]=0; }//消去相应的位置的方块 } }

由于可能导致连锁反应，所以我们需要在不能消掉之前一直循环

注意要每次处理完当前的所有能消去的方块（无论是哪个颜色的方块都不能再消了）之后再继续处理掉落.

while(check()){//如果还能继续消方块 //按颜色依次处理并全部消去后， for(int i=0;i<5;i++){ int k=-1; for(int j=0;j<7;j++){ if(mp[i][j]){ mp[i][++k]=mp[i][j]; } } for(int j=k+1;j<7;j++){ mp[i][j]=0; } }//再掉落 }

---

存储初始图：

对于每一步，我们都开一个局部数组存储初始图，这样方便在回溯时恢复状态.

int upd[15][15];//update数组存一开始的情况 memset(upd,0,sizeof upd); for(int i=0;i<5;i++){ for(int j=0;j<7;j++)upd[i][j]=mp[i][j]; }//在回溯的时候再把mp的值变回upd

---

dfs总体框架：

bool dfs(当前进行到的步数){ 1.记录输入时的初始图 如果有架空的方块，则架空的方块掉落 while(当前的状态可以消去方块){ 枚举，找到各个颜色可以消去的方块并消去 如果有架空的方块，掉落 } 判断当前是否为全部消除，如果全部消除就回溯 for()依次枚举点，dfs(step+1) 以上都没得到答案，图变回初始图，回溯 }

其一，注意只要没有得到答案，回溯时都需要变成初始图；否则要记录答案.

其二，一开始时的初始图由于是从上一步直接移动来的，所以可能架空，需要进行掉落操作.

其三，注意处理边界条件，不要越界；数组大小也要统一.

其四，题目中的坑点：虽然说了颜色不多于10种，从1开始顺序编号，相同数字表示相同颜色，但是却有一组数据给出了1,2,3,4,6的颜色（没有5），所以在枚举颜色时，最好枚举1到10，反正如果没有这种颜色就不会处理，不会影响正确性.

其五，题目的输入很坑，给的数据转换成图高是7，宽是5，但是直接输入的话是$5\ast 7$的图，所以要么在输入时进行转换，要么在输入后把左右交换变为上下交换. 这里我采用的是后者.

程序实现

#include<bits/stdc++.h> using namespace std; int n,mp[15][15]; bool check(){ for(int i=0;i<5;i++) for(int j=0;j<7;j++){ if(!mp[i][j])continue; if(j<5&&mp[i][j]==mp[i][j+1]&&mp[i][j]==mp[i][j+2])return true; if(i<3&&mp[i][j]==mp[i+1][j]&&mp[i][j]==mp[i+2][j])return true; } return false; }//check函数判断当前图中是否有可以消去的方块，只要找得到连续三个就返回true struct answer{ int l,r,op; }ans[10];//存答案的结构体 bool ck[15][15],q[15][15]; void deal(int x,int y,int dirc){ if(dirc==1){//dirc==1表示有一行可以消去的方块 if(x>2)return ;//边界处理降低时间常数 if(ck[x+1][y]==true&&ck[x+2][y]==true){ q[x][y]=1; q[x+1][y]=1; q[x+2][y]=1; if(ck[x+3][y]==true&&x+3<5){ q[x+3][y]=1; if(ck[x+4][y]==true&&x+4<5)q[x+4][y]=1; } } } else if(dirc==2){//dirc==2表示有一列可以消去的方块 if(y>4)return ; if(ck[x][y+1]==true&&ck[x][y+2]==true){ q[x][y]=1; q[x][y+1]=1; q[x][y+2]=1; if(ck[x][y+3]==true&&y+3<7){ q[x][y+3]=1;//如果有第四个 if(ck[x][y+4]==true&&y+4<7)q[x][y+4]=1; }//这个地方写挂过，只有当第四个存在，第五个才能连在一起 //不能把第四个和第五个写成并列的形式 } } }//deal标记所有能够被消去的这个颜色的方块 bool dfs(int step){ if(step>n+1)return false; int upd[15][15]; memset(upd,0,sizeof upd); for(int i=0;i<5;i++){ for(int j=0;j<7;j++)upd[i][j]=mp[i][j]; }//upd存原图 for(int i=0;i<5;i++){ int k=-1; for(int j=0;j<7;j++){ if(mp[i][j]){ mp[i][++k]=mp[i][j]; } } for(int j=k+1;j<7;j++){ mp[i][j]=0; } }//drop while(check()){//当还能消方块时 for(int k=1;k<=10;k++){ //又是一个坑，可能跳过一些颜色 memset(ck,false,sizeof ck); int tot=0; for(int i=0;i<5;i++){ for(int j=0;j<7;j++){ if(mp[i][j]==k){ ck[i][j]=true; tot++; } } }//方块为当前颜色的，打上标记 if(tot<3&&tot){ for(int i=0;i<5;i++){ for(int j=0;j<7;j++)mp[i][j]=upd[i][j]; } return false; }//小剪枝，该颜色方块剩下的数量不可被完全消去 memset(q,false,sizeof q); for(int i=0;i<5;i++){ for(int j=0;j<7;j++){ if(ck[i][j]){ deal(i,j,1); deal(i,j,2); } } } for(int i=0;i<5;i++){ for(int j=0;j<7;j++){ if(q[i][j])mp[i][j]=0; } } }//消除这些位置的方块 for(int i=0;i<5;i++){ int k=-1; for(int j=0;j<7;j++){ if(mp[i][j]){ mp[i][++k]=mp[i][j]; } } for(int j=k+1;j<7;j++){ mp[i][j]=0; } }//drop } bool flag=true; for(int i=0;i<5;i++){ for(int j=0;j<7;j++){ if(mp[i][j]>0){ flag=false; break; } } if(!flag)break; }//确定是否全部消除 if(flag&&step==n+1){ return true; }//如果全部消除且满足步数要求，直接返回 else if(!flag&&step==n+1){//未全部清空 for(int i=0;i<5;i++){ for(int j=0;j<7;j++)mp[i][j]=upd[i][j]; }//坑点！回溯时记得把图恢复一开始记录的样子 return false; } else if(flag&&step<n+1){//全部清空但步数不满足 for(int i=0;i<5;i++){ for(int j=0;j<7;j++)mp[i][j]=upd[i][j]; }//同上 return false; } for(int i=0;i<5;i++){ for(int j=0;j<7;j++){ if(!mp[i][j])continue; if(i<4){ swap(mp[i][j],mp[i+1][j]); bool w=dfs(step+1); if(w){ ans[step].l =i,ans[step].r =j; ans[step].op =1; return true; } swap(mp[i][j],mp[i+1][j]);//不满足，恢复原图 }//右移操作 if(i>0&&!mp[i-1][j]){ swap(mp[i-1][j],mp[i][j]); bool w=dfs(step+1); if(w){ ans[step].l =i,ans[step].r =j; ans[step].op =-1; return true; } swap(mp[i-1][j],mp[i][j]);//不满足，恢复原图 }//左移操作 } } for(int i=0;i<5;i++){ for(int j=0;j<7;j++)mp[i][j]=upd[i][j]; }//回溯时一定要记得恢复原图 return false; } int main(){ memset(mp,0,sizeof mp); scanf("%d",&n); for(int i=0,w;i<5;i++){ scanf("%d",&w); int j=-1; while(w){ mp[i][++j]=w; scanf("%d",&w); } } if(!dfs(1))printf("-1\n"); else { for(int i=1;i<=n;i++){ printf("%d %d %d\n",ans[i].l ,ans[i].r ,ans[i].op ); } } return 0; }

题后总结

一个好的程序员应该在编程时就避免错误的发生，而不是在编程结束之后再调试，这样很浪费时间，我们要确保自己想的和写的一样，比如这里“连续多个方块”的情况，就要考虑好：只有在连续四个时才可能出现连续五个的情况（当然由于我这种暴力的写法所以实际上根本不用判断连续四个及以上，因为这样会由连续的第二个，第三个……通过连续三个的情况来判断出来）. 又比如在回溯的时候需要变回原值，这是一个套路，必须在程序中实现. 还有对于题目的理解，不能曲解题意了（对于有序输出颜色的理解）.

另外，输入格式等也要注意，不能想到什么写什么，而要看是否满足题意.