专栏文章

题解：P1312 [NOIP2011 提高组] Mayan 游戏

llihongru
P1312题解参与者 8已保存评论 9

文章操作

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

当前评论
9 条
当前快照
1 份
快照标识符
@miqel9rx
此快照首次捕获于
2025/12/04 03:31
3 个月前
此快照最后确认于
2025/12/04 03:31
3 个月前
查看原文

题目分析

本题没有什么特别的办法，只能尝试每一个步骤的走法。说到尝试，就一定是搜索了。不过本题的搜索比较复杂，夹杂了模拟。我认为本题难度主要在代码上。
为了方便，我们将本题的编号起点 (0,0)(0, 0) 调整为 (1,1)(1, 1)，并在最后输出时 −1-1。

移动-move 函数

先不管如何搜索操作步骤。对于每一次移动块，先要交换块，然后进行删除，删除后出现新的空，需要进行下落，下落后又有新的块……由此，我们可以先来实现一个移动的函数。
CPP
void move(int x, int y, int k){
	swap(mp[x][y], mp[x+k][y]); // 1交换
	down(); // 2下落
	while (remove()) down(); // 3判定并继续下落
}
其中 remove 表示消除（返回值为是否进行了至少一组的消除），down 表示下落。

下落-down 函数

接下来我们就可以开始完成这两个函数了。先来看 down 函数。
首先我们知道，下落不会引起列交换。所以我们对于 55 列，分别处理。快速的办法就是新建一个数组，将所有不为 00 的块拷贝进去（不留空白），再重新拷贝出来。例如一列 00102300010230，进入数组后 12300001230000，再回到这一列就变成了 12300001230000，比朴素向下找方便。
CPP
void down(){
	for (int i = 1; i <= 5; i++){
		int b[10] = {}, cnt = 0; // 此处将b数组清0了
		for (int j = 1; j <= 7; j++){
			if (mp[i][j]) b[++cnt] = mp[i][j]; // 加入新数组
		}
		for (int j = 1; j <= 7; j++){
			mp[i][j] = b[j]; // 移回原数组，并覆盖多余部分
		}
	}
}

移除-remove 函数

接下来就是 remove 函数。这是比较复杂的一个函数。因为可能出现题目描述中“共享方块”的问题，我们不能直接修改原数组。这个时候我们就需要一个辅助数组了。
一旦找到某个块可以作为消除块的中间，标记到辅助数组。最终把辅助数组中的标记和原数组中的被标记位置一同清空，并检查是否消除了块。一定注意，空白不能作为一个“空白块”的中间位置，遇到空白要跳过，否则可能会出现死循环。
CPP
bool remove(){
	for (int i = 1; i <= 5; i++){
		for (int j = 1; j <= 7; j++){
			if (!mp[i][j]) continue; // 空白块要跳过
			if (mp[i-1][j] == mp[i][j] && mp[i+1][j] == mp[i][j])
				v[i-1][j] = v[i][j] = v[i+1][j] = 1; // 标记横向块
			if (mp[i][j-1] == mp[i][j] && mp[i][j+1] == mp[i][j])
				v[i][j-1] = v[i][j] = v[i][j+1] = 1; // 标记纵向块
		}
	}
	bool ret = false; // 寻找是否消除
	for (int i = 1; i <= 5; i++){
		for (int j = 1; j <= 7; j++){
			if (v[i][j]) {
				mp[i][j] = v[i][j] = 0;
				ret = true;
			}
		}
	}
	return ret;
}
三个函数都完成了，接下来就可以进入重点的搜索部分了。

搜索-dfs 函数

要说搜索，我们可以枚举 5×75 \times 7 个块判断消除，这是完全没有问题的。最坑的地方就是回溯，因为无法还原出原状态。
当然，解决办法也很简单——再加辅助数组。在找之前，先把原数据复制过来，每次回溯再复制回去。
另外，除了剪枝，我们还得使用数组记录答案，最终还需要一个判断是否完成的函数 check，具体怎么写见下一部分。
CPP
void dfs(int x){
	if (flag) return ;
	if (check()){
		for (int i = 1; i <= n; i++){
			cout << ans[i][1] << " " << ans[i][2] << " " << ans[i][3] << endl;
		}
		flag = true;
		return ;
	}
	if (x > n) return ;
	int tmp[10][10];
	memcpy(tmp, mp, sizeof tmp);
	for (int i = 1; i <= 5; i++){
		for (int j = 1; j <= 7; j++){
			if (!mp[i][j]) break;
			if (i < 5){
				ans[x][1] = i - 1;
				ans[x][2] = j - 1;
				ans[x][3] = 1;
				move(i, j, 1); dfs(x+1);
				memcpy(mp, tmp, sizeof mp);
			}
			if (i > 1 && !mp[i-1][j]){
				ans[x][1] = i - 1;
				ans[x][2] = j - 1;
				ans[x][3] = -1;
				move(i, j, -1); dfs(x+1);
				memcpy(mp, tmp, sizeof mp);
			}
		}
	}
}
注意：11 优先于 −1-1，一定要先搜索向右移动。向右移动，右边只要不为空，即可移动。向左移动需要注意不能移到空白处。

检查-check 函数

非常简单，由于我们可以保证在执行 check 函数时，数组状态完全合法，所以只找第一横行是否有块即可。
CPP
bool check(){
	for (int i = 1; i <= 5; i++){
		if (mp[i][1]) return false;
	}
	return true;
}

关于 Hack 数据

Hack 数据仅需 11 步即可完成，但它的输入 nn 大于 11。我的代码最开始被 Hack 了，是因为判断向右的时候多加了不相同才换的条件。对于这种情况，需要通过“无效交换”“拖延”步数，所以不能加“不相同才换”的条件。

题目总结与参考代码

本题主要难度是如何进行搜索，以及搜索过程中的模拟。调代码的难度也是比较大的，可以通过加辅助输出或者 return 来调错。
CPP
#include <bits/stdc++.h>
using namespace std;

int n, mp[10][10], v[10][10], ans[10][5];
bool flag;

void down(){
	for (int i = 1; i <= 5; i++){
		int b[10] = {}, cnt = 0;
		for (int j = 1; j <= 7; j++){
			if (mp[i][j]) b[++cnt] = mp[i][j];
		}
		for (int j = 1; j <= 7; j++){
			mp[i][j] = b[j];
		}
	}
}

bool remove(){
	for (int i = 1; i <= 5; i++){
		for (int j = 1; j <= 7; j++){
			if (!mp[i][j]) continue;
			if (mp[i-1][j] == mp[i][j] && mp[i+1][j] == mp[i][j])
				v[i-1][j] = v[i][j] = v[i+1][j] = 1;
			if (mp[i][j-1] == mp[i][j] && mp[i][j+1] == mp[i][j])
				v[i][j-1] = v[i][j] = v[i][j+1] = 1;
		}
	}
	bool ret = false;
	for (int i = 1; i <= 5; i++){
		for (int j = 1; j <= 7; j++){
			if (v[i][j]) {
				mp[i][j] = v[i][j] = 0;
				ret = true;
			}
		}
	}
	return ret;
}

bool check(){
	for (int i = 1; i <= 5; i++){
		if (mp[i][1]) return false;
	}
	return true;
}

void move(int x, int y, int k){
	swap(mp[x][y], mp[x+k][y]);
	down();
	while (remove()) down();
}

void dfs(int x){
	if (flag) return ;
	if (check()){
		for (int i = 1; i <= n; i++){
			cout << ans[i][1] << " " << ans[i][2] << " " << ans[i][3] << endl;
		}
		flag = true;
		return ;
	}
	if (x > n) return ;
	int tmp[10][10];
	memcpy(tmp, mp, sizeof tmp);
	for (int i = 1; i <= 5; i++){
		for (int j = 1; j <= 7; j++){
			if (!mp[i][j]) break;
			if (i < 5){
				ans[x][1] = i - 1;
				ans[x][2] = j - 1;
				ans[x][3] = 1;
				move(i, j, 1); dfs(x+1);
				memcpy(mp, tmp, sizeof mp);
			}
			if (i > 1 && !mp[i-1][j]){
				ans[x][1] = i - 1;
				ans[x][2] = j - 1;
				ans[x][3] = -1;
				move(i, j, -1); dfs(x+1);
				memcpy(mp, tmp, sizeof mp);
			}
		}
	}
}

int main(){
	cin >> n;
	for (int i = 1; i <= 5; i++){
		int p = 0, x; cin >> x;
		while (x) {
			mp[i][++p] = x;
			cin >> x;
		}
	}
	dfs(1);
	if (!flag) 
		cout << -1 << endl;
	return 0;
}

评论

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

正在加载评论...