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];// 上方补0while (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]--; // 总数减1cnt[g[x][y]]--; // 对应颜色方块数减1g[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;
}