NOIP2011提高组.玛雅游戏

题目

185. 玛雅游戏

算法标签: 模拟, 搜索, $dfs$, 剪枝优化

思路

可行性剪枝

• 如果某个颜色的格子数量少于$3$一定无解
• 因为要求字典序最小, 因此当一个格子左边有格子, 不能向左移动, 应该向右移动, 具体来说当前位置向左移动$(x,y,-1)$, 但是左边格子向右移动$(x-1,y,1)$, 字典序是更小的
  因为每个格子整体上向右移动

时间复杂度$35^5$大概$5\times 10^7$

*详细注释版代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int R = 7, C = 5, S = 5;
const int TYPE = 11;

int n; // 需要通关的步数
int g[C][R]; // 游戏棋盘，5列7行（x:0-4, y:0-6）
int bg[S][C][R]; // 备份棋盘状态，用于回溯，bg[step][x][y]表示第step步时的棋盘状态
int cnt[TYPE]; // 统计每种颜色方块的数量，cnt[0]是所有方块总数，cnt[1-10]是各颜色方块数
int bcnt[S][TYPE]; // 备份方块数量统计，用于回溯
bool st[C][R]; // 标记哪些方块需要被消除

struct Path {
	int x, y, d; // 记录移动路径：x,y是坐标，d是方向(1右,-1左)
} path[5]; // 存储每一步的移动

// 移动方块并处理消除和掉落
void move(int a, int b, int c) {
	// 交换两个方块
	swap(g[a][b], g[c][b]);

	while (true) {
		bool flag = true; // 标记是否还有可以消除的方块

		// 处理悬空方块，让方块下落
		for (int x = 0; x < 5; x++) {
			int z = 0;
			// 压缩非空方块到列底部
			for (int y = 0; y < 7; y++)
				if (g[x][y])
					g[x][z++] = g[x][y];
			// 上方补0
			while (z < 7) g[x][z++] = 0;
		}

		// 检查可以消除的方块
		memset(st, 0, sizeof st);
		for (int x = 0; x < 5; x++)
			for (int y = 0; y < 7; y++)
				if (g[x][y]) {
					// 检查水平方向是否有3个或以上连续相同方块
					int l = x, r = x;
					while (l - 1 >= 0 && g[l - 1][y] == g[x][y]) l--;
					while (r + 1 < 5 && g[r + 1][y] == g[x][y]) r++;
					if (r - l + 1 >= 3) {
						st[x][y] = true;
						flag = false;
					}
					else {
						// 检查垂直方向是否有3个或以上连续相同方块
						l = r = y;
						while (l - 1 >= 0 && g[x][l - 1] == g[x][y]) l--;
						while (r + 1 < 7 && g[x][r + 1] == g[x][y]) r++;

						if (r - l + 1 >= 3) {
							st[x][y] = true;
							flag = false;
						}
					}
				}

		// 如果没有可以消除的方块，退出循环
		if (flag) break;

		// 消除标记的方块
		for (int x = 0; x < 5; x++)
			for (int y = 0; y < 7; y++)
				if (st[x][y]) {
					cnt[0]--; // 总数减1
					cnt[g[x][y]]--; // 对应颜色方块数减1
					g[x][y] = 0; // 清空该位置
				}
	}
}

// 深度优先搜索解决玛雅难题
bool dfs(int u) {
	// 如果达到目标步数且所有方块都被消除，返回成功
	if (u == n) return !cnt[0];

	// 剪枝：如果有颜色只剩1或2个方块，不可能消除完，提前返回
	for (int i = 1; i <= 10; i++)
		if (cnt[i] == 1 || cnt[i] == 2)
			return false;

	// 备份当前状态
	memcpy(bg[u], g, sizeof g);
	memcpy(bcnt[u], cnt, sizeof cnt);

	// 枚举所有可能的移动
	for (int x = 0; x < 5; x++)
		for (int y = 0; y < 7; y++)
			if (g[x][y]) {
				// 尝试向右移动
				int nx = x + 1;
				if (nx < 5) {
					path[u] = {x, y, 1}; // 记录路径
					move(x, y, nx); // 执行移动
					if (dfs(u + 1)) return true; // 递归搜索
					// 回溯
					memcpy(g, bg[u], sizeof g);
					memcpy(cnt, bcnt[u], sizeof cnt);
				}

				// 尝试向左移动
				nx = x - 1;
				if (nx >= 0 && !g[nx][y]) { // 左边为空才能移动（否则会与向右移动重复）
					path[u] = {x, y, -1}; // 记录路径
					move(x, y, nx); // 执行移动
					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 x = 0; x < 5; x++) {
		int t, y = 0;
		while (scanf("%d", &t), t) {
			cnt[0]++; // 总数增加
			cnt[t]++; // 对应颜色方块数增加
			g[x][y++] = t; // 放置方块
		}
	}

	// 深度优先搜索
	if (dfs(0)) {
		// 输出解决方案
		for (int i = 0; i < n; i++)
			printf("%d %d %d\n", path[i].x, path[i].y, path[i].d);
	}
	else {
		// 无解
		puts("-1");
	}

	return 0;
}

精简注释版代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int R = 7, C = 5, S = 5;
const int TYPE = 11;

int n;
int g[C][R], bg[S][C][R];
int cnt[TYPE], bcnt[S][TYPE];
bool vis[C][R];

struct Path {
	int x, y, d;
} path[S];

// 处理方块移动和消除
void move(int a, int b, int na) {
	swap(g[a][b], g[na][b]);

	while (true) {
		bool flag = true;

		// 处理悬空方块，让它们下落
		for (int x = 0; x < C; ++x) {
			int z = 0;
			// 压缩非空方块到列底部
			for (int y = 0; y < R; ++y) {
				if (g[x][y]) {
					g[x][z++] = g[x][y];
				}
			}
			// 填充剩余位置为空
			while (z < R) {
				g[x][z++] = 0;
			}
		}

		memset(vis, false, sizeof vis);

		for (int x = 0; x < C; ++x) {
			for (int y = 0; y < R; ++y) {
				if (g[x][y]) {
					// 检查横向
					int l = x, r = x;
					while (l - 1 >= 0 && g[l - 1][y] == g[x][y]) l--;
					while (r + 1 < C && g[r + 1][y] == g[x][y]) r++;
					if (r - l + 1 >= 3) {
						vis[x][y] = true;
						flag = false;
					}
						// 检查纵向
					else {
						int u = y, d = y;
						while (u - 1 >= 0 && g[x][u - 1] == g[x][y]) u--;
						while (d + 1 < R && g[x][d + 1] == g[x][y]) d++;
						if (d - u + 1 >= 3) {
							vis[x][y] = true;
							flag = false;
						}
					}
				}
			}
		}

		if (flag) break;

		// 消除标记的方块
		for (int x = 0; x < C; ++x) {
			for (int y = 0; y < R; ++y) {
				if (vis[x][y]) {
					cnt[0]--;
					cnt[g[x][y]]--;
					g[x][y] = 0;
				}
			}
		}
	}
}

bool dfs(int u) {
	if (u == n) return !cnt[0];

	for (int i = 1; i <= 10; ++i) {
		if (cnt[i] == 1 || cnt[i] == 2) return false;
	}

	// 备份当前状态
	memcpy(bg[u], g, sizeof g);
	memcpy(bcnt[u], cnt, sizeof cnt);

	// 尝试所有可能的移动
	for (int x = 0; x < C; ++x) {
		for (int y = 0; y < R; ++y) {
			if (g[x][y]) {
				// 向右移动
				if (x + 1 < C) {
					path[u] = {x, y, 1};
					move(x, y, x + 1);
					if (dfs(u + 1)) return true;
					memcpy(g, bg[u], sizeof g);
					memcpy(cnt, bcnt[u], sizeof cnt);
				}

				// 向左移动
				if (x - 1 >= 0 && !g[x - 1][y]) {
					path[u] = {x, y, -1};
					move(x, y, x - 1);
					if (dfs(u + 1)) return true;
					memcpy(g, bg[u], sizeof g);
					memcpy(cnt, bcnt[u], sizeof cnt);
				}
			}
		}
	}

	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;

	for (int x = 0; x < C; ++x) {
		int t, y = 0;
		while (cin >> t, t) {
			cnt[0]++;
			cnt[t]++;
			g[x][y++] = t;
		}
	}

	if (dfs(0)) {
		for (int i = 0; i < n; ++i) {
			cout << path[i].x << " " << path[i].y << " " << path[i].d << "\n";
		}
	}
	else {
		cout << -1 << "\n";
	}

	return 0;
}