題目

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;
}