只用看checkAndEliminate()、virtualGravity()和move()三个函数有没有问题即可,因为其他的是老师写的让我补全代码(没错就tm是补全代码我都能写出bug来qwq)
#include <bits/stdc++.h>
#define debug cout<<"debug"<<endl;
using namespace std;
struct S {
int x, y, d; //记录移动过程
} ans[5];
int n;
int g[5][7], bg[5][5][7]; //bg备份数组,用于回溯恢复
int nTColor[5][7];//临时存储颜色
int cnt[15], bcnt[5][15]; //cnt[i]表示第i种颜色的方块数量
bool st[5][7]; //用来标记方块是否被消除
pair<int,int> checkP1[6]={{1,0},{-1,0},{1,0},{0,1},{0,-1},{0,1}},
checkP2[6]={{2,0},{-2,0},{-1,0},{0,2},{0,-2},{0,-1}};//消除要判断的两个点的坐标
queue<pair<int,int> > q;
bool isInMap(int x,int y){
return (x>=0&&x<5&&y>=0&&y<7);
}
bool checkAndEliminate(){//检查是否有要消除的并顺便消除
bool res=false;
for(int i=0;i<5;++i){
for(int j=0;j<7;++j){
nTColor[i][j]=g[i][j];
}
}
for(int i=0;i<5;++i){
for(int j=0;j<7&&g[i][j];++j){
while(!q.empty()){
q.pop();
}
q.push({i,j});
while(!q.empty()){//类bfs搜索消除
//debug
int nx=q.front().first,ny=q.front().second;
for(int k=0;k<6;++k){
int _x1_=nx+checkP1[k].first,_x2_=nx+checkP2[k].first,
_y1_=ny+checkP1[k].second,_y2_=ny+checkP2[k].second;
if(isInMap(_x1_,_y1_)&&isInMap(_x2_,_y2_)&&g[_x1_][_y1_]==nTColor[nx][ny]&&g[_x2_][_y2_]==nTColor[nx][ny]){
q.push({_x1_,_y1_});
q.push({_x2_,_y2_});
g[_x1_][_y1_]=0;
g[_x2_][_y2_]=0;
g[nx][ny]=0;
res=true;
}
}
q.pop();
}
}
}
return res;
}
void virtualGravity(){//模拟重力下落
for(int i=0;i<5;++i){
for(int j=0;j<7;++j){
if(g[i][j]){
int t=j;
while(t>0&&!g[i][t-1]){
g[i][t-1]=g[i][t];
g[i][t]=0;
--t;
}
}
}
}
}
void move(int a, int b, int c)
{
swap(g[a][b], g[c][b]); //交换两个方块
virtualGravity();//万一有一个是空的,需要判断重力下落
while(checkAndEliminate()){
//debug
virtualGravity();
}
}
bool dfs(int u)
{
if (u == n)
return cnt[0] == 0; //搜索结束,如果方块全部消除则有解
for (int i = 1; i <= 10; i ++) //可行性剪枝,当某种颜色的方块数量小于等于2时,无法消除,则一定无解
if (cnt[i] <= 2 && cnt[i] >= 1) //漂亮
return false;
// 开始进行递归
memcpy(bg[u], g, sizeof g); //备份g,用来恢复现场 将g覆盖到bg的第u步中
memcpy(bcnt[u], cnt, sizeof cnt); // 备份cnt
//选择1个方块进行移动
for (int i = 0; i < 5; i ++)
for (int j = 0; j < 7; j ++)
if (g[i][j]) { //不为0有颜色 有方块
int c = i + 1; //向右移动到c列
if (c < 5) { // 不超出5列
ans[u] = {i, j, 1}; // 第u步记录一下
move(i, j, c);
if(dfs(u + 1)) return true; // 递归到下一步,如果返回1则表示也可以成功
memcpy(g, bg[u], sizeof g); //不成功回溯,恢复现场
memcpy(cnt, bcnt[u], sizeof cnt);
}
c = i - 1; //向左移动 同样道理,但是可以进行一下剪枝
if (c >= 0 && g[c][j] == 0) { //向左移动,而左边方块也有颜色,进行最优性剪枝
ans[u] = {i, j, -1};
move(i, j, c);
if (dfs(u + 1)) return true;
memcpy(g, bg[u], sizeof g); //回溯,恢复现场
memcpy(cnt, bcnt[u], sizeof cnt);
}
}
return false;
}
int main()
{
scanf("%d", &n); // 通关部署
for (int i = 0; i < 5; i ++) { //枚举列 一共5列
int c, j = 0; //j表示行
while (scanf("%d", &c), c != 0) { // 颜色为0结束这组输出
g[i][j ++] = c; // 第i列的第j个数字是c 往下一列赋值颜色
cnt[0] ++; //方块的总数 // 方块的数量
cnt[c] ++; //c颜色的方块数量
}
}
if (dfs(0)) { //从第0步暴力搜索 完成在n步通过 输出解决方案 一定会发生数字的
// 不对的时候 回溯的 数组要不变 备份数组
for (int i = 0; i < n; i ++) // 输出列, 行, 朝哪边
printf("%d %d %d\n", ans[i].x, ans[i].y, ans[i].d);
}
else puts("-1"); // 输出不来
return 0;
}