题解 P1312 【Mayan游戏】
蒟蒻也能写出来的AC代码！（其实主要是为了纪念一遍AC这道题……）可能存在多余的地方和更好的剪枝，因此这份代码仅供参考，可以进一步优化。
这种数据范围贼小的题一看就是搜索。搜索的策略是：两重for循环枚举每一个点，对于一个点总是先考虑往右移（优先级更高），如果左边是0的话才考虑往左移（若左边是非0的话不必了，因为这种情况就是左边的点往右移，但它已经被研究过了）。移动完了就要消去，由于消去可能不止一次所以我们要用循环。
此外还要注意保存的方式。我是将数组完全复制到一个临时数组里。这样能保证原数组不会受到后续步骤消去的影响。
一些细节请看注释。
#include <iostream>
#include <cstdio>
using namespace std;
int n, a[10][10], temp, jie1[10], jie2[10], jie3[10];
void check(){
bool flag=true;
for(int i=1; i<=5; i++)
if(a[i][1])
flag = false;
if(flag){
for(int i=1; i<=n; i++)
printf("%d %d %d\n", jie1[i]-1, jie2[i]-1, jie3[i]);
exit(0);
}
}
bool func(){//消去及调整函数
bool s[10][10]={0}, flag=false;//flag标记有无进行消去
for(int i=1; i<=5; i++){
for(int j=1; a[i][j]; j++){
int k=i+1;//看x轴上以(i,j)为起点的块儿是否满足条件
for( ; k<=5; k++)
if(a[k][j]!=a[i][j])//找寻终点
break;
if(k-i>=3){//要是长度达标就标记下来，一会儿同时消去
for(int l=i; l<k; l++)
s[l][j] = true;
flag = true;
}
k = j+1;//看y轴上以(i,j)为起点的块儿是否满足条件
for( ; k<=7; k++)
if(a[i][j]!=a[i][k])
break;
if(k-j>=3){
for(int l=j; l<k; l++)
s[i][l] = true;
flag = true;
}
}
}
for(int i=1; i<=5; i++)
for(int j=1; j<=7; j++)
if(s[i][j])
a[i][j] = 0;//消去
if(!flag) return false;//要是没有消去就可以停下了
for(int i=1; i<=5; i++)
for(int j=1; j<=7; j++)
if(a[i][j]==0){//调整以防止悬空的出现
int k=j+1;
for( ; k<=7; k++)
if(a[i][k])
break;
a[i][j] = a[i][k];
a[i][k] = 0;
}
return true;
}
void dfs(int x){//以步数作为dfs的参数
for(int i=1; i<=5; i++){
for(int j=1; a[i][j]!=0; j++){
if(i!=5 && a[i][j]!=a[i+1][j] && a[i+1][j]!=0){//要是右边非0的话
int tem[10][10];
for(int ii=0; ii<=9; ii++)
for(int jj=0; jj<=9; jj++)
tem[ii][jj] = a[ii][jj];//复制到临时数组里
int tmp=a[i][j];
a[i][j] = a[i+1][j];
a[i+1][j] = tmp;
jie1[x] = i;
jie2[x] = j;
jie3[x] = 1;//保存这一步的答案
while(func()) ;//消去。要循环！
if(x==n) check();//要是步数够了就看看是否完全消去。
else dfs(x+1);
for(int ii=0; ii<=9; ii++)
for(int jj=0; jj<=9; jj++)
a[ii][jj] = tem[ii][jj];//优雅地回溯
}
if(i!=5 && a[i+1][j]==0){//要是右边为0的话
int tem[10][10];
for(int ii=0; ii<=9; ii++)
for(int jj=0; jj<=9; jj++)
tem[ii][jj] = a[ii][jj];
int k;
for(k=j-1; k>=1; k--)
if(a[i+1][k])
break;
k++;
a[i+1][k] = a[i][j];
a[i][j] = 0;
jie1[x] = i;
jie2[x] = j;
jie3[x] = 1;
for(int e=j; e<=6; e++){
a[i][e] = a[i][e+1];
a[i][e+1] = 0;
}
while(func()) ;
if(x==n) check();
else dfs(x+1);
for(int ii=0; ii<=9; ii++)
for(int jj=0; jj<=9; jj++)
a[ii][jj] = tem[ii][jj];
}
if(i!=1 && a[i-1][j]==0){//要是左边为0的话
int tem[10][10];
for(int ii=0; ii<=9; ii++)
for(int jj=0; jj<=9; jj++)
tem[ii][jj] = a[ii][jj];
int k;
for(k=j-1; k>=1; k--)
if(a[i-1][k])
break;
k++;
a[i-1][k] = a[i][j];
a[i][j] = 0;
jie1[x] = i;
jie2[x] = j;
jie3[x] = -1;
for(int e=j; e<=6; e++){
a[i][e] = a[i][e+1];
a[i][e+1] = 0;
}
while(func()) ;
if(x==n) check();
else dfs(x+1);
for(int ii=0; ii<=9; ii++)
for(int jj=0; jj<=9; jj++)
a[ii][jj] = tem[ii][jj];
}
}
}
}
int main(){
cin>>n;
for(int i=1; i<=5; i++){
int tmp = 0;
while(cin>>temp){
if(!temp) break;
a[i][++tmp] = temp;
}
}//读入数据，为了方便我们将左上角的设为(1, 1)，在输出时减一即可
dfs(1);
cout<<"-1";//要是没有exit掉那就只能是无解了
return 0;
}
```cpp