要不是徐妈让我做，我这辈子都不可能碰这道题的。
这是我做过的代码最长的非数据结构题，模拟题最长也就一百来行，这道题第一次原生态（包括注释和调试）交上去有214行，删掉调试输出和合并一些if后也有174行。
况且我一点优化都没加，纯种裸暴搜，加了优化不知道有多复杂。不过这题暴力能过就是了，吸氧前最大点1618ms，吸氧后774ms。
思路
整个过程可以分为 移动 --> 移动后的掉落 --> 消除 --> 消除后的掉落 --> 继续消除 --> 继续消除后的掉落 --> ...
移动
显然，相同颜色的块是不用移动的。其次，如果在中间左移右移是等价的，为了让字典序尽可能小，我们肯定尽可能选择右移。那么左移就只可能发生在当前块左边是空的情况下。
然后移动的话交换就行了，掉落是下一步的事。
移动使用 $mv(x,y,s)$ 函数，其中 $(x,y)$ 是移动的块，$s=1$ 代表右移，$s=-1$ 代表左移。$drop()$就是掉落，后面就讲。
inline void mv(int x,int y,int s) //之前已经保证没有越界
{
swap(stat.s[x][y],stat.s[x+s][y]);
drop();
}消除
由于 $drop()$ 是一样的，所以把消除讲完后再讲。
消除其实就是找到连续的块打一个 $mark[x][y]=1$ 的标记就行了。这里采用dfs，如果满足条件（即连续个数>=3）那么在回溯时打上标记即可。
既然说了是裸暴搜，我用的方法自然就很暴力，直接双重循环查找起点然后作为起点往上下左右搜索就行了。
既然还要实现掉落后还要删除的问题，我就把它返回一个bool，如果还有可以删除的块，也就是 $marked>0$ 就返回true再做一遍。需要消除的地方这么写就行了：
while (update());下面是整个消除的代码：
bool dfs_update(int x,int y,int fx,int fy,int step) //dfs标记所有可以消除的
{
bool can;
if (step>=3) can=1;
else can=0;
if (stat.s[x+fx][y+fy]==stat.s[x][y]) can=can || dfs_update(x+fx,y+fy,fx,fy,step+1);
if (can) mark[x][y]=1;
return can;
}
inline bool update() //消去所有可以消的方块
{
for (int i=1;i<=5;i++)
{
for (int j=1;j<=7;j++)
{
if (!stat.s[i][j]) continue;
dfs_update(i,j,0,1,1); //纵向上
dfs_update(i,j,0,-1,1); //纵向下
dfs_update(i,j,1,0,1); //横向右
dfs_update(i,j,-1,0,1); //横向左
}
}
int marked=0;
for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)
marked+=mark[i][j];
drop();
return marked;
}掉落
两种掉落其实原理是一样的，把空格填上就行了。当然，消除后的掉落还要兼任一个把标记过的方块删掉（也就是赋值为0）的操作。虽然只有消除后掉落需要这么做，但移动后掉落反正也没有标记，统一用这个也没有任何问题。
inline void drop()
{
for (int i=1;i<=5;i++)
{
for (int j=1;j<=7;j++)
{
if (!mark[i][j]) continue;
mark[i][j]=0;
stat.s[i][j]=0;
}
for (int j=1;j<=7;j++)
{
if (stat.s[i][j]) continue; //找到空格删除
int cnt=0;
for (int k=j+1;k<=7;k++)
{
if (!stat.s[i][k]) continue;
stat.s[i][j+cnt]=stat.s[i][k];
cnt++;
stat.s[i][k]=0;
break;
}
}
}
}检查是否清空
直接检查每一列第一个是否为0就行了。
inline bool check()
{
for (int i=1;i<=5;i++)
if (stat.s[i][1])
return 0;
return 1;
}整个dfs
就是dfs的标准格式，需要提前备份一下初始状态方便还原，还有就是如果已经找到了（即 $can=1$）或者步数超了就可以直接退出。主体就是二重循环枚举交换哪个方块。
void dfs(int step)
{
if (can) return;
if (check()) //已经全部消除完，输出方案
{
can=1;
for (int i=1;i<step;i++) printf("%d %d %d\n",cur[i][0]-1,cur[i][1]-1,cur[i][2]);
return;
}
if (step==n+1) return;
MAP now;
for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)
now.s[i][j]=stat.s[i][j]; //备份
for (int i=1;i<=5;i++)
{
for (int j=1;j<=7;j++)
{
if (!now.s[i][j]) continue;
if (i==5) //在最右边一列只可能往左移
{
if (now.s[i-1][j]) continue;
mv(i,j,-1); //移动
cur[step][0]=i; cur[step][1]=j; cur[step][2]=-1; //记录当前移动方式
while (update()); //消除
dfs(step+1);
for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)
stat.s[i][j]=now.s[i][j]; //还原
continue;
}
// 右移
if (stat.s[i][j]!=stat.s[i+1][j])
{
mv(i,j,1);
cur[step][0]=i; cur[step][1]=j; cur[step][2]=1;
while (update());
dfs(step+1);
for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)
stat.s[i][j]=now.s[i][j];
}
if (i>=2 && !now.s[i-1][j]) //左边为空往左移
{
mv(i,j,-1);
cur[step][0]=i; cur[step][1]=j; cur[step][2]=-1;
while (update());
dfs(step+1);
for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)
stat.s[i][j]=now.s[i][j];
}
}
}
}代码
struct MAP{
int s[10][10];
} stat;
int n,m,a,b,c,cur[10][3]; //0->x;1->y;2->left/right
bool can=0;
bool mark[10][10];
inline void drop()
{
for (int i=1;i<=5;i++)
{
for (int j=1;j<=7;j++)
{
if (!mark[i][j]) continue;
mark[i][j]=0;
stat.s[i][j]=0;
}
for (int j=1;j<=7;j++)
{
if (stat.s[i][j]) continue; //找到空格删除
int cnt=0;
for (int k=j+1;k<=7;k++)
{
if (!stat.s[i][k]) continue;
stat.s[i][j+cnt]=stat.s[i][k];
cnt++;
stat.s[i][k]=0;
break;
}
}
}
}
inline void mv(int x,int y,int s) //保证没有越界
{
swap(stat.s[x][y],stat.s[x+s][y]);
drop();
}
inline bool check()
{
for (int i=1;i<=5;i++)
if (stat.s[i][1])
return 0;
return 1;
}
bool dfs_update(int x,int y,int fx,int fy,int step) //标记所有可以消除的
{
bool can;
if (step>=3) can=1;
else can=0;
if (stat.s[x+fx][y+fy]==stat.s[x][y]) can=can || dfs_update(x+fx,y+fy,fx,fy,step+1);
if (can) mark[x][y]=1;
return can;
}
inline bool update() //消去所有可以消的方块
{
for (int i=1;i<=5;i++)
{
for (int j=1;j<=7;j++)
{
if (!stat.s[i][j]) continue;
dfs_update(i,j,0,1,1); //纵向上
dfs_update(i,j,0,-1,1); //纵向下
dfs_update(i,j,1,0,1); //横向右
dfs_update(i,j,-1,0,1); //横向左
}
} //mark checked
int marked=0;
for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)
marked+=mark[i][j];
drop();
return marked;
}
void dfs(int step)
{
if (can) return;
if (check()) //已经全部消除完，校验每列第一个即可
{
can=1;
for (int i=1;i<step;i++) printf("%d %d %d\n",cur[i][0]-1,cur[i][1]-1,cur[i][2]);
return;
}
if (step==n+1) return;
MAP now;
for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)
now.s[i][j]=stat.s[i][j]; //备份
for (int i=1;i<=5;i++)
{
for (int j=1;j<=7;j++)
{
if (!now.s[i][j]) continue;
if (i==5) //只可能往左移
{
if (now.s[i-1][j]) continue;
mv(i,j,-1);
cur[step][0]=i; cur[step][1]=j; cur[step][2]=-1;
while (update());
dfs(step+1);
for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)
stat.s[i][j]=now.s[i][j];
continue;
}
// 右移
if (stat.s[i][j]!=stat.s[i+1][j])
{
mv(i,j,1);
cur[step][0]=i; cur[step][1]=j; cur[step][2]=1;
while (update());
dfs(step+1);
for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)
stat.s[i][j]=now.s[i][j];
}
if (i>=2 && !now.s[i-1][j]) //左边为空往左移
{
mv(i,j,-1);
cur[step][0]=i; cur[step][1]=j; cur[step][2]=-1;
while (update());
dfs(step+1);
for (int i=1;i<=5;i++)
for (int j=1;j<=7;j++)
stat.s[i][j]=now.s[i][j];
}
}
}
}
int main()
{
n=read();
for (int i=1;i<=5;i++)
{
int m=0;
a=read();
while (a)
{
stat.s[i][++m]=a;
a=read();
}
} //read checked
dfs(1);
if (!can) printf("-1");
return 0;
}