蒟蒻20pts求调,悬赏关注(
查看原帖
蒟蒻20pts求调,悬赏关注(
511811
崛起的滑稽楼主2024/6/11 22:06

只用看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;
}
2024/6/11 22:06
加载中...