专栏文章

P1312 [NOIP 2011 提高组] Mayan 游戏题解

hhexuchen
P1312题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqbr7g0
此快照首次捕获于
2025/12/04 02:12
3 个月前
此快照最后确认于
2025/12/04 02:12
3 个月前
查看原文
题目传送门
更好的阅读体验？

题目大意

一款消消乐游戏，有 7×57 \times 5 的棋盘。每次可以横向挪动一个方块，相同颜色的 33 个方块可以消除。求消除所有方块的最小次数。

思路分析

一道毒瘤的模拟、深搜题。
此题思路不难。枚举每一个方块所有可能的移动，用 dfs 搜索即可。回溯有些麻烦，要先用一个辅助数组存下原数组，回溯时将原数组的值替换成辅助数组的值。
注意直接搜索会 TLE，所以要加剪枝。在向左移动方块时要判断左边是否为空。如果为空，则没有移动的必要，直接退出。
坑点见此贴

代码分解

这题难难在代码上。为了方便，本题解采用数组的顺序存储棋盘，即左上角的坐标是 (1,1)(1,1)。
注：只展示重要的函数，零散小函数不展示

down 函数

该函数用于实现将某一个方块落下。
CPP
void down(int x,int y){
	if(s[x][y]==0){ //格子为空则没必要下落
		return ;
	}
	for(int i=x;i<7;i++){ //遍历到底部
		if(s[i+1][y]==0){ //下面为空
			swap(s[i+1][y],s[i][y]);
		}
		else{ //落到方块上了
			break;
		}
	}
}

move 函数

该函数用于移动方块。
CPP
void move(int x,int y,int r,int c){
	swap(s[x][y],s[r][c]); //交换方块位置
	down(r,c);
	for(int i=x-1;i>=1;i--){ //方块下落
		down(i,y);
	}
}

proccess 函数

该函数用于消除 33 个连着的方块并下落。但是题目有一个坑：
（如图 5）当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除
所以判断不能直接在原数组上判断，要用辅助数组进行判断，原数组进行消除。
CPP
void proccess(){
	a_to_b(s,s2); //这是自己定义的一个简单函数，负责将原数组 s 的值复制给辅助数组 s2
	for(int i=1;i<=7;i++){ //横向的三个
		for(int j=1;j<=3;j++){
			if(s2[i][j]==s2[i][j+1] && s2[i][j+1]==s2[i][j+2]){ //有三个连在一起的，注意用辅助数组判断
				s[i][j]=s[i][j+1]=s[i][j+2]=0; //用原数组消除
			}
		}
	}
	for(int i=1;i<=5;i++){ //纵向的三个
		for(int j=1;j<=5;j++){
			if(s2[j+1][i]==s2[j+2][i] && s2[j+2][i]==s2[j+3][i]){
				s[j+1][i]=s[j+2][i]=s[j+3][i]=0;
			}
		}
	}
	for(int i=7;i>=1;i--){ //记得下落
		for(int j=1;j<=5;j++){
			down(i,j);
		}
	}
}

dfs 函数

CPP
void dfs(int step){
	if(check()){ //check 负责判断棋盘是否全空
		print(); //print 负责输出
		return ;
	}
	if(step>n){ //步数超了
		return ;
	}
	int s3[8][6]; //辅助数组，负责回溯
	for(int j=1;j<=5;j++){ //先列再行
		for(int i=7;i>=1;i--){ //从大到小（因为代码是倒着存的，这样可以使字典序最小）
			if(s[i][j]==0){
				continue;
			}
			if(j<=4){ //可以右移
				a_to_b(s,s3); //辅助数组更新
				ans1[step]=j-1;
				ans2[step]=7-i;
				ans3[step]=1;
				move(i,j,i,j+1); //移方块
				for(int k=1;k<=(num/3+1);k++){ //注意可能会存在连续消除的情况，num 为方块个数
					proccess();
				}
				dfs(step+1);
				a_to_b(s3,s); //回溯
			}
			if(j>=2 && s[i][j-1]==0){ //左移，剪枝
				a_to_b(s,s3);
				ans1[step]=j-1;
				ans2[step]=7-i;
				ans3[step]=-1;
				move(i,j,i,j-1);
				for(int k=1;k<=(num/3+1);k++){
					proccess();
				}
				dfs(step+1);
				a_to_b(s3,s);
			}
		}
	}
}

AC 代码

CPP
#include <bits/stdc++.h>
using namespace std;
int n,s[8][6],s2[8][6],ans1[6],ans2[6],ans3[6],num=0;
void a_to_b(int (&a)[8][6],int (&b)[8][6]){
	for(int i=1;i<=7;i++){
		for(int j=1;j<=5;j++){
			b[i][j]=a[i][j];
		}
	}
}
void down(int x,int y){
	if(s[x][y]==0){
		return ;
	}
	for(int i=x;i<7;i++){
		if(s[i+1][y]==0){
			swap(s[i+1][y],s[i][y]);
		}
		else{
			break;
		}
	}
}
void move(int x,int y,int r,int c){
	swap(s[x][y],s[r][c]);
	down(r,c);
	for(int i=x-1;i>=1;i--){
		down(i,y);
	}
}
void proccess(){
	a_to_b(s,s2);
	for(int i=1;i<=7;i++){
		for(int j=1;j<=3;j++){
			if(s2[i][j]==s2[i][j+1] && s2[i][j+1]==s2[i][j+2]){
				s[i][j]=s[i][j+1]=s[i][j+2]=0;
			}
		}
	}
	for(int i=1;i<=5;i++){
		for(int j=1;j<=5;j++){
			if(s2[j+1][i]==s2[j+2][i] && s2[j+2][i]==s2[j+3][i]){
				s[j+1][i]=s[j+2][i]=s[j+3][i]=0;
			}
		}
	}
	for(int i=7;i>=1;i--){
		for(int j=1;j<=5;j++){
			down(i,j);
		}
	}
}
bool check(){
	for(int i=1;i<=7;i++){
		for(int j=1;j<=5;j++){
			if(s[i][j]!=0){
				return false;
			}
		}
	}
	return true;
}
void print(){
	for(int i=1;i<=n;i++){
		cout<<ans1[i]<<' '<<ans2[i]<<' '<<ans3[i]<<'\n';
	}
	exit(0);
}
void dfs(int step){
	if(check()){
		print();
		return ;
	}
	if(step>n){
		return ;
	}
	int s3[8][6];
	for(int j=1;j<=5;j++){
		for(int i=7;i>=1;i--){
			if(s[i][j]==0){
				continue;
			}
			if(j<=4){
				a_to_b(s,s3);
				ans1[step]=j-1;
				ans2[step]=7-i;
				ans3[step]=1;
				move(i,j,i,j+1);
				for(int k=1;k<=(num/3+1);k++){
					proccess();
				}
				dfs(step+1);
				a_to_b(s3,s);
			}
			if(j>=2 && s[i][j-1]==0){
				a_to_b(s,s3);
				ans1[step]=j-1;
				ans2[step]=7-i;
				ans3[step]=-1;
				move(i,j,i,j-1);
				for(int k=1;k<=(num/3+1);k++){
					proccess();
				}
				dfs(step+1);
				a_to_b(s3,s);
			}
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=5;i++){
		int a;
		for(int j=7;j>=0;j--){
			cin>>a;
			if(a==0){
				break;
			}
			s[j][i]=a;
			num++;
		}
	}
	dfs(1);
    cout<<-1;
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...