题解 P1312 【Mayan游戏】
题解
传送门：透彻
此题就相当与是一道大型搜索模拟题，需要耐心，极考验码力；
因为代码比较长，所以建议大家多写函数，尽量不要都写在一起；
提前交代数组
int map[N][N]; //输入的图
int ans[N][5]; //输出的答案
int last[N][N][N]; //后面会讲
bool xiao[N][N]; //后面会讲
下面我讲一下其中的核心函数：
1.copy（复制）：
我们要把当前的原始状态复制
为什么要复制呢，回溯时要用；
但不能使用二维数组了，要定义一个三维数组
last[d][i][j]：第d步时在i行j列的原状态；
void copy(int x){
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
last[x][i][j]=map[i][j];
}2.update（更新游戏的状态）：
这个比较简单，就是把该掉下去的掉下去；
定义一个x为这个这个方块下0的个数，然后模拟一下；
void update(){
for(int i=1;i<=5;i++){
int x=0;
for(int j=1;j<=7;j++){
if(!map[i][j])x++;
else{
map[i][j-x]=map[i][j];
map[i][j]=0;
}
}
}
}3.remove（消除）：
题目要求一定要行或列连续3个才能消除；
但一定不能遇到3个连续的就消；
例如：
bool remove(){
int flag=0;
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++){
if(i-1>=1&&i+1<=5&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j]&&map[i][j]){
xiao[i-1][j]=1;xiao[i+1][j]=1;xiao[i][j]=1;flag=1;
}
if(j-1>=1&&j+1<=7&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1]&&map[i][j]){
xiao[i][j]=1;xiao[i][j+1]=1;xiao[i][j-1]=1;flag=1;
}
}
if(!flag)return 0;
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
if(xiao[i][j]){
xiao[i][j]=0;
map[i][j]=0;
}
return 1;
}图5中的要是先消3个，那剩下的就不能消了，就WA了；
我枚举的i,j是中间方块的坐标；
而且使用的是bool型，为了后面判断是否可以继续去消；
4.move （移动）：
移动比较简单；就是用到了之前函数；
要注意，可能消除后还可以更新，所以要使用while循环；
void move(int i,int j,int x){
int tmp=map[i][j];
map[i][j]=map[i+x][j];
map[i+x][j]=tmp;
update();
while(remove())update();
}5.check（判断是否都消除了）：
这个更简单了；
因为所有方块都掉落了，所以直接判断最后一行都为0就行了；
bool check(){
for(int i=1;i<=5;i++)
if(map[i][1])return 0;
return 1;
}DFS的剪枝：
1.相同颜色的方块可以跳过（显而易见）；
2.还有一个比较难想的剪枝：
结论：只有右边有方块才move，左边没有方块才move；
证明（自己瞎写的）：
（你正在搜i列）若左面有方块，那么你会在搜i-1列时将其右移，和你在i列时左移是等效的，所以可以减掉；
code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdlib>
#define ll long long
#define N 10
using namespace std;
int read()
{
int X=0,w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
int n,map[N][N],ans[N][5],last[N][N][N],xiao[N][N];
bool remove(){
int flag=0;
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++){
if(i-1>=1&&i+1<=5&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j]&&map[i][j]){
xiao[i-1][j]=1;xiao[i+1][j]=1;xiao[i][j]=1;flag=1;
}
if(j-1>=1&&j+1<=7&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1]&&map[i][j]){
xiao[i][j]=1;xiao[i][j+1]=1;xiao[i][j-1]=1;flag=1;
}
}
if(!flag)return 0;
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
if(xiao[i][j]){
xiao[i][j]=0;
map[i][j]=0;
}
return 1;
}
bool check(){
for(int i=1;i<=5;i++)
if(map[i][1])return 0;
return 1;
}
void copy(int x){
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
last[x][i][j]=map[i][j];
}
void update(){
for(int i=1;i<=5;i++){
int wow=0;
for(int j=1;j<=7;j++){
if(!map[i][j])wow++;
else{
if(!wow)continue;
map[i][j-wow]=map[i][j];
map[i][j]=0;
}
}
}
}
void move(int i,int j,int x){
int tmp=map[i][j];
map[i][j]=map[i+x][j];
map[i+x][j]=tmp;
update();
while(remove())update();
}
void dfs(int x){
if(check()){
for(int i=1;i<=n;i++){
if(i!=1)printf("\n");
for(int j=1;j<=3;j++)
printf("%d ",ans[i][j]);
}
exit(0);
}
if(x==n+1)return;
copy(x);
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++){
if(map[i][j]){
if(i+1<=5&&map[i][j]!=map[i+1][j]){
move(i,j,1);
ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=1;
dfs(x+1);
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
map[i][j]=last[x][i][j];
ans[x][1]=-1;ans[x][2]=-1;ans[x][3]=-1;
}
if(i-1>=1&&map[i-1][j]==0){
move(i,j,-1);
ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=-1;
dfs(x+1);
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
map[i][j]=last[x][i][j];
ans[x][1]=-1;ans[x][2]=-1;ans[x][3]=-1;
}
}
}
}
int main()
{
// freopen("Manya.in","r",stdin);
// freopen("Manya.out","w",stdout);
n=read();
for(int i=1;i<=5;i++){
for(int j=1;j<=8;j++){
int x=read();
if(x==0)break;
map[i][j]=x;
}
}
memset(ans,-1,sizeof(ans));
dfs(1);
puts("-1");
return 0;
}