题目链接：https://www.luogu.org/problemnew/show/P1312
我的第一篇题解！！
当然感谢ZAGER 的提示，他的链接https://www.cnblogs.com/ZAGER/p/9535526.html
这道题是一个大暴搜，真实考验了我的代码能力……
写函数是个好习惯，思路清晰明了。
分步骤
定义map[i][j]表示当前地图的情况，last[x][i][j]表示第x步时地图原貌，ans[x][i]记录第x步时的操作
check()检查是否被消完，当然根据规则只要检查最下面一行是否都被消完即可；
bool check()
{
for(int i=;i<=;i++)
{
if(map[i][]) return ;
}
return ;
}
update()进行掉落过程，我们从下往上搜，记录当前map有值的时候其下面有几个空行
void update()//掉落过程
{
for(int i=;i<=;i++)
{
int down=;
for(int j=;j<=;j++)
{
if(!map[i][j]) down++;
else
{
if(!down) continue;
map[i][j-down]=map[i][j];
map[i][j]=;
}
}
}
}
重点在这（对于我来说）
转换移动的操作，没好好看题，移动的时候不一定只和其他方块互换，也可以拖到悬空，然后掉落，所以互换后要检查掉落情况
void move(int x,int y,int z)//转换移动
{
int mem=map[x][y];
map[x][y]=map[x+z][y];
map[x+z][y]=mem;
update();
while(remove()) update();//被消除后进行掉落
}
remove()用来进行消除过程。为了满足条件图5情况，我们先记录在进行消除。
int remove()//消除过程
{
bool flag=;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if(i>=&&i<=&&map[i][j]&&map[i][j]==map[i-][j]&&map[i][j]==map[i+][j])
{
xx[i-][j]=;xx[i][j]=;xx[i+][j]=;flag=;
}
if(j>=&&j<=&&map[i][j]&&map[i][j]==map[i][j+]&&map[i][j]==map[i][j-])
{
xx[i][j]=;xx[i][j-]=;xx[i][j+]=;flag=;
}
}
}//先记录再消除，满足图五情况
if(!flag) return ;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if(xx[i][j])
{
map[i][j]=;
xx[i][j]=;
}
}
}
return ;
}
还有几个无关紧要（也很重要）的小函数，代码里有注解
还有一个重要的剪枝，就是“向左的时候如果左方并非是空，则跳过（否则可以选择其左侧方块右移，这样字典序更小）”；
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int n;
int map[][],last[][][],ans[][];//map当前地图，；last第几步移动前的地图；ans是前为步数，后为答案
int xx[][];
bool check()
{
for(int i=;i<=;i++)
{
if(map[i][]) return ;
}
return ;
} void memory(int x)
{
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
last[x][i][j]=map[i][j];//记录第x步时地图的原貌
}
}
} void update()//掉落过程
{
for(int i=;i<=;i++)
{
int down=;
for(int j=;j<=;j++)
{
if(!map[i][j]) down++;
else
{
if(!down) continue;
map[i][j-down]=map[i][j];
map[i][j]=;
}
}
}
} int remove()//消除过程
{
bool flag=;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if(i>=&&i<=&&map[i][j]&&map[i][j]==map[i-][j]&&map[i][j]==map[i+][j])
{
xx[i-][j]=;xx[i][j]=;xx[i+][j]=;flag=;
}
if(j>=&&j<=&&map[i][j]&&map[i][j]==map[i][j+]&&map[i][j]==map[i][j-])
{
xx[i][j]=;xx[i][j-]=;xx[i][j+]=;flag=;
}
}
}//先记录再消除，满足图五情况
if(!flag) return ;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if(xx[i][j])
{
map[i][j]=;
xx[i][j]=;
}
}
}
return ;
}
void move(int x,int y,int z)//转换移动
{
int mem=map[x][y];
map[x][y]=map[x+z][y];
map[x+z][y]=mem;
update();
while(remove()) update();//被消除后进行掉落
} void recover(int x)
{
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
map[i][j]=last[x][i][j];
}
}
ans[x][]=;ans[x][]=;ans[x][]=;
}
void dfs(int x)
{
if(check())
{
for(int i=;i<=n;i++)
{
if(i!=) printf("\n");
for(int j=;j<=;j++)
{
printf("%d ",ans[i][j]);
}
}
exit();
}
if(x==n+) return ;
memory(x);
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if(map[i][j])
{
if(i<=&&map[i][j]!=map[i+][j])
{
move(i,j,);
ans[x][]=i-;ans[x][]=j-;ans[x][]=;
dfs(x+);
recover(x);//恢复原地图和ans
}
}
if(i>=&&(!map[i-][j]))
{
move(i,j,-);
ans[x][]=i-;ans[x][]=j-;ans[x][]=-;
dfs(x+);
recover(x);
}
}
} } int main()
{
scanf("%d",&n);
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
int x;
scanf("%d",&x);
if(x==) break;
map[i][j]=x;
}
}
dfs();//从第一步开始搜
printf("-1\n");
return ;
}