玛雅游戏

GitHub跳转原题关系图返回列表

按字典序枚举移动做恰好 n 步 DFS，用「整体标记→消除→掉落」循环结算局面，再以颜色计数、同色空转、左移等价、失败记忆化四条安全剪枝压缩搜索树。

OJ: roj

题目 ID: 3078

难度:提高+/省选-

标签:搜索DFS剪枝模拟python

创建: 2026-10-01 14:49

更新: 2026-10-07 13:50

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结
  4. 图示解析

形式化题目

棋盘为 77 行 55 列的网格，坐标 x∈[0,4]x \in [0,4] 从左到右、y∈[0,6]y \in [0,6] 从下到上，每格为空或放一个颜色为 1∼101 \sim 10 的方块；方块不悬空（每列方块从 y=0y=0 起连续堆叠），且初始局面不含任何三连。

一步移动选定有方块的格子 (x,y)(x,y)，沿横向 g∈{1,−1}g \in \{1,-1\} 拖动一格：

  • 目标格 (x+g,y)(x+g,y) 有方块：两方块交换位置；
  • 目标格 为空：该方块从原竖列抽出（原列上方方块随即下落补位），落到目标位置后继续掉落，直到落在这列当前最上方。

移动后立即结算：只要任一行或任一列出现连续 ⩾3\geqslant 3 个同色方块，就把所有满足条件的方块同时消除（行列共享的方块只消一次，多组同时触发），然后上方方块整体掉落；掉落过程中不判定消除，如此循环直到局面稳定。

给定正整数 nn，求恰好 nn 步后棋盘为空的移动序列；多组解时输出按 (x,y,g)(x,y,g) 逐位比较（gg 中 11 优先于 −1-1）字典序最小的一组，无解输出 −1-1。

样例初始局面与答案三步移动（· 为空格）：

text
 y\x   0   1   2   3   4
  3    .   .   .   .   4
  2    .   .   4   .   3
  1    .   1   3   1   4
  0    1   2   2   3   2

依次走 (2,1,1)(2,1,1)、(3,1,1)(3,1,1)、(3,0,1)(3,0,1) 后棋盘恰好清空（逐步结算过程见文末「图示解析」）。

把「棋盘」看作状态、「移动 + 结算」看作转移，本题就是：在一张隐式状态图上，求长度恰好为 nn、终点为空棋盘、且移动序列字典序最小的路径；无解要求穷尽整棵搜索树后才能断言。

正解

思路

朴素做法：直接 DFS 枚举。 每层枚举所有合法 (x,y,g)(x,y,g)（最多 5×7×2=705 \times 7 \times 2 = 70 个），模拟结算得到新局面，递归 nn 层；剩余步数为 00 时检查棋盘是否为空。这个框架本身就是正确答案的骨架，但裸跑规模太大：分支随方块数增长，且无解数据必须穷尽全树。实测去掉全部剪枝后，三组数据的搜索节点与耗时如下（Python 3，本机）：

数据 nn 无剪枝节点 无剪枝耗时 剪枝后节点 剪枝后耗时
mayan6（无解） 4 1.95×1061.95\times10^{6} 11.3 s 5.1×1045.1\times10^{4} 0.29 s
mayan7 5 4.18×1064.18\times10^{6} 24.5 s 1.2×1051.2\times10^{5} 0.65 s
mayan10 5 6.16×1066.16\times10^{6} 36.8 s 2.5×1052.5\times10^{5} 1.46 s

题面时限 11 秒，裸 DFS 必然超时。优化全部来自对搜索树的结构性观察，且每条剪枝都只删「必败」或「与更小字典序解重复」的子树，不删任何真解。

观察 1：枚举顺序就是字典序，第一个解即最小解。 所有候选解等长（都是 nn 行），按 xx 升序、yy 升序、每个位置先 g=1g=1 后 g=−1g=-1 的顺序深搜，先搜到的解在每一位上都不劣于后搜到的解。因此不必收集全部解再比较，回溯时第一次到达叶子且棋盘为空就直接输出。

观察 2：左移交换与右邻右移是同一条转移。 (x,y,−1)(x,y,-1) 若目标 (x−1,y)(x-1,y) 有方块，效果等于把 (x−1,y)(x-1,y) 的方块右移——二者交换的方块对相同、新局面完全相同。而 (x−1,y,1)(x-1,y,1) 的 xx 更小、在观察 1 的顺序里先被枚举，所以任何含「左移交换」的解都能替换成一个字典序更小、局面轨迹相同的解：字典序最小解中不可能出现左移交换，整棵子树可剪。注意左移到空位（抽落）没有等价的更小移动，必须保留——样例数据 mayan2 的解 (4,0,-1) 正是左移到空位，剪掉它会把正解误判成无解。

观察 3：同色交换是空转步。 目标方块与移动方块同色时，交换后局面与移动前完全一致，这一步不推进「清空」的任何进度，只会把同一局面复制成多耗一步的子树。直接剪掉它与所有公开题解的实现一致；本题数据上去掉该剪枝重跑全部 10 组，输出完全不变。

观察 4：颜色计数是不变量。 方块只能被三连消除，某颜色全场只剩 1∼21 \sim 2 块时永远凑不出三连，它将永远留在棋盘上，整个子树必败，整层剪断。

观察 5：失败局面可记忆化。 一个局面之后能否在剩余步数内清空，只取决于「局面 + 剩余步数」，与路径无关；把搜过且失败的 (局面, 剩余步数) 记入集合，重复到达时直接返回。无解数据要穷尽全树，这条剪枝收益最大（观察 3 已剪掉原地耗步，记忆化不会与「空转等待」交互出漏洞）。

四条剪枝分别消除四类浪费：空转步、左右对称的重复子树、必败局面的重复搜索、无望颜色的继续展开。上表右两列就是它们把 6×1066\times10^{6} 压到 2.5×1052.5\times10^{5} 的效果。

结算模拟是正确性的另一半，有三个容易写错的点，整体流程如下图：

graph TD
  A["moved：交换 或 抽落（原列补位、落至列顶）"] --> B["settle：扫描所有行/列的 >=3 连续同色"]
  B --> C{"存在三连?"}
  C -- 否 --> DONE["局面稳定，返回"]
  C -- 是 --> D["本轮全部三连同时标记（行列共享只记一次）"]
  D --> E["被标记方块整体删除"]
  E --> F["各列过滤空位，上方方块掉落压实"]
  F -- 掉落不判定，回到扫描 --> B
  1. 整体标记：先把本轮所有三连（横、竖、行列共享）标在同一张 5×75\times7 布尔网格上，再统一删除——边扫边删会让后续三连的判定建立在已残缺的棋盘上，行列共享的情形（题面图 5）会漏消。
  2. 掉落不判定：删除后只压实、不立即检查，回到扫描入口再判——否则掉落中途的半成品局面会触发规则不允许的消除。
  3. 恰好 nn 步：若棋盘在剩余步数 >0>0 时已清空，后续没有方块可移动，枚举自然为空，该分支判负——恰好语义在叶子检查里自然成立。

代码

主解把观察 1 的枚举序写进三重循环顺序，把四条剪枝分别放在移动生成（越界、同色、左移交换）、递归入口（颜色计数、失败记忆化）两处，结算由 three_run_grid + settle 完成：

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 14:49
# update_at: 2026-10-01 14:49

import sys

WIDTH = 5   # 棋盘列数
HEIGHT = 7  # 棋盘行数


def three_run_grid(board: list[list[int]]) -> list[list[bool]] | None:
    """把本轮该消除的方块标记在 5x7 网格上：行列共享的方块只记一次；无三连返回 None。"""
    dead = [[False] * HEIGHT for _ in range(WIDTH)]
    found = False
    for x in range(WIDTH):
        col = board[x]
        for y in range(len(col) - 2):  # 每列内部竖向三连
            if col[y] == col[y + 1] == col[y + 2]:
                found = True
                dead[x][y] = dead[x][y + 1] = dead[x][y + 2] = True
    for y in range(HEIGHT):
        for x in range(WIDTH - 2):
            # 不足 7 格的列把缺位读作 0，颜色从 1 开始，0 天然不会三连同色
            run = [board[i][y] if y < len(board[i]) else 0 for i in range(x, x + 3)]
            if run[0] and run[0] == run[1] == run[2]:
                found = True
                dead[x][y] = dead[x + 1][y] = dead[x + 2][y] = True
    return dead if found else None


def settle(board: list[list[int]]) -> list[list[int]]:
    """消除 → 掉落 循环到棋盘稳定。"""
    while dead := three_run_grid(board):
        for x in range(WIDTH):
            col = board[x]
            for y, d in enumerate(dead[x]):
                if d:
                    col[y] = 0                  # 先整体标记消除，不能边判边删
        board[:] = [[c for c in col if c] for col in board]  # 再整体掉落
    return board


def moved(board: list[list[int]], x: int, y: int, g: int) -> list[list[int]] | None:
    """把 (x, y) 的方块沿 g 方向拖动一格并结算，返回新棋盘；无意义移动返回 None。"""
    nx = x + g
    if not 0 <= nx < WIDTH:
        return None
    nb = [col[:] for col in board]
    if y < len(nb[nx]):                          # 目标位置有方块：交换
        if nb[nx][y] == nb[x][y]:
            return None                          # 同色交换后棋盘不变，白白浪费一步
        nb[nx][y], nb[x][y] = nb[x][y], nb[nx][y]
    else:                                        # 目标位置为空：抽落后掉落到 min(y, 列高)
        nb[nx].insert(min(y, len(nb[nx])), nb[x].pop(y))
    return settle(nb)


def dfs(board: list[list[int]], left: int, failed: set[tuple]) -> list[tuple[int, int, int]] | None:
    """还剩 left 步时能否清空；按 x→y→(右,左) 的枚举顺序，第一个解就是字典序最小的。"""
    state = (tuple(map(tuple, board)), left)     # 可哈希局面：只用来记住"到此必败"
    if state in failed:
        return None
    if left == 0:
        return [] if all(not col for col in board) else None
    counts = [0] * 11                            # 颜色 1~10 的方块计数
    for col in board:
        for c in col:
            counts[c] += 1
    if any(0 < v < 3 for v in counts):           # 某颜色只剩 1~2 个，永远凑不出三连
        failed.add(state)
        return None
    for x in range(WIDTH):
        for y in range(len(board[x])):
            for g in (1, -1):
                nx = x + g
                if not 0 <= nx < WIDTH:
                    continue
                # 左移交换 = 左邻方块右移，那个局面字典序更小且已先枚举过，直接跳过
                if g == -1 and y < len(board[nx]):
                    continue
                nb = moved(board, x, y, g)
                if nb is None:
                    continue
                tail = dfs(nb, left - 1, failed)
                if tail is not None:
                    return [(x, y, g)] + tail
    failed.add(state)
    return None


def solve() -> None:
    """读入棋盘，DFS 恰好 n 步，按字典序输出方案或 -1。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    board: list[list[int]] = []
    for _ in range(WIDTH):                       # 每竖列自下而上给出，以 0 结尾
        col: list[int] = []
        v = next(data)
        while v != 0:
            col.append(v)
            v = next(data)
        board.append(col)

    moves = dfs(board, n, set())
    if moves is None:
        print(-1)
    else:
        print("\n".join(f"{x} {y} {g}" for x, y, g in moves))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 17:40
 * update_at: 2026-10-06 17:40
 */
// 玛雅游戏：恰好 n 步清空棋盘，输出字典序最小的移动序列，无解输出 -1。
// 做法：按 x、y、右移优先的顺序 DFS，遇到第一个解即为最小字典序；配合
// 四条剪枝（同色空转、左移交换、颜色计数不足 3、失败局面记忆化）压缩搜索树。
#include <cstring>
#include <iostream>
#include <set>
#include <string>
using namespace std;

typedef long long ll;

const int W = 5; // 棋盘列数
const int H = 7; // 棋盘行数

int n;                 // 要求恰好移动的步数
int a[W][H];           // a[x][y] 为第 x 列自下而上第 y 个方块的颜色，仅 y < h[x] 有效
int h[W];              // h[x] 为第 x 列当前方块数
bool dead[W][H];       // dead[x][y] 标记本轮该被消除的方块

int ans_x[64];         // 第 i 步移动的列
int ans_y[64];         // 第 i 步移动的行
int ans_g[64];         // 第 i 步移动的方向

set<string> failed;    // 记录「该局面 + 剩余步数」已确认无解，避免重复搜索

// 把当前局面和剩余步数编码成可哈希的字符串，用作记忆化的键。
string encode_state(int left) {
    string s;
    s.push_back(char(left));
    for (int x = 0; x < W; x++) {
        for (int y = 0; y < h[x]; y++) {
            s.push_back(char(a[x][y]));
        }
        s.push_back(char(0)); // 用 0 分隔各列
    }
    return s;
}

// 扫描所有行和列，把本轮该消除的方块整体标记在 dead 上；无三连返回 false。
bool mark_dead() {
    memset(dead, 0, sizeof(dead));
    bool found = false;
    // 竖向三连
    for (int x = 0; x < W; x++) {
        for (int y = 0; y + 2 < h[x]; y++) {
            if (a[x][y] == a[x][y + 1] && a[x][y + 1] == a[x][y + 2]) {
                found = true;
                dead[x][y] = dead[x][y + 1] = dead[x][y + 2] = true;
            }
        }
    }
    // 横向三连，不足 7 格的列把缺位读作颜色 0（颜色从 1 开始，0 不会凑成三连）
    for (int y = 0; y < H; y++) {
        for (int x = 0; x + 2 < W; x++) {
            int c0 = (y < h[x]) ? a[x][y] : 0;
            int c1 = (y < h[x + 1]) ? a[x + 1][y] : 0;
            int c2 = (y < h[x + 2]) ? a[x + 2][y] : 0;
            if (c0 != 0 && c0 == c1 && c1 == c2) {
                found = true;
                dead[x][y] = dead[x + 1][y] = dead[x + 2][y] = true;
            }
        }
    }
    return found;
}

// 消除与掉落的循环：整体标记删除后压实，掉落过程不判定消除，直到局面稳定。
void settle() {
    while (mark_dead()) {
        for (int x = 0; x < W; x++) {
            int w = 0;
            for (int y = 0; y < h[x]; y++) {
                if (!dead[x][y]) {
                    a[x][w] = a[x][y];
                    w++;
                }
            }
            h[x] = w;
        }
    }
}

// 把第 x 列第 y 个方块沿 g 方向拖动一格；无意义移动返回 false。
bool apply_move(int x, int y, int g) {
    int nx = x + g;
    if (nx < 0 || nx >= W) return false;
    if (y < h[nx]) { // 目标位置有方块：交换
        if (a[nx][y] == a[x][y]) return false; // 同色交换后局面不变，白走一步
        int tmp = a[nx][y];
        a[nx][y] = a[x][y];
        a[x][y] = tmp;
    } else { // 目标位置为空：从原列抽出并落向目标列顶部
        int v = a[x][y];
        for (int k = y; k + 1 < h[x]; k++) a[x][k] = a[x][k + 1];
        h[x]--;
        int p = (y < h[nx]) ? y : h[nx]; // 落点不会高于目标列当前高度
        for (int k = h[nx]; k > p; k--) a[nx][k] = a[nx][k - 1];
        a[nx][p] = v;
        h[nx]++;
    }
    settle();
    return true;
}

// 还剩 left 步时能否把棋盘清空；枚举顺序保证第一个解就是字典序最小的解。
bool dfs(int left) {
    string key = encode_state(left);
    if (failed.count(key)) return false;
    if (left == 0) { // 恰好 n 步走完，检查是否清空
        for (int x = 0; x < W; x++) {
            if (h[x] > 0) return false;
        }
        return true;
    }
    int cnt[11] = {0}; // 颜色 1~10 的方块计数
    for (int x = 0; x < W; x++) {
        for (int y = 0; y < h[x]; y++) {
            cnt[a[x][y]]++;
        }
    }
    for (int c = 1; c <= 10; c++) {
        if (cnt[c] > 0 && cnt[c] < 3) { // 某颜色只剩 1~2 块，永远凑不出三连，必败
            failed.insert(key);
            return false;
        }
    }
    for (int x = 0; x < W; x++) {
        for (int y = 0; y < h[x]; y++) {
            for (int gi = 0; gi < 2; gi++) { // 先右移后左移，字典序更小的先枚举
                int g = (gi == 0) ? 1 : -1;
                int nx = x + g;
                if (nx < 0 || nx >= W) continue;
                // 左移交换等于左邻方块右移，而后者字典序更小且已被枚举过，剪掉
                if (g == -1 && y < h[nx]) continue;
                // 备份当前局面，试走一步后递归，失败再还原
                int sa[W][H];
                int sh[W];
                for (int i = 0; i < W; i++) {
                    sh[i] = h[i];
                    for (int j = 0; j < h[i]; j++) sa[i][j] = a[i][j];
                }
                if (apply_move(x, y, g)) {
                    ans_x[n - left] = x;
                    ans_y[n - left] = y;
                    ans_g[n - left] = g;
                    if (dfs(left - 1)) return true;
                }
                for (int i = 0; i < W; i++) {
                    h[i] = sh[i];
                    for (int j = 0; j < sh[i]; j++) a[i][j] = sa[i][j];
                }
            }
        }
    }
    failed.insert(key);
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int x = 0; x < W; x++) {
        int v;
        cin >> v;
        while (v != 0) {
            a[x][h[x]] = v;
            h[x]++;
            cin >> v;
        }
    }
    if (dfs(n)) {
        for (int i = 0; i < n; i++) {
            cout << ans_x[i] << " " << ans_y[i] << " " << ans_g[i] << "\n";
        }
    } else {
        cout << -1 << "\n";
    }
    return 0;
}

复杂度

  • 时间：搜索树深度为 nn（数据中 n⩽5n \leqslant 5），每层分支不超过 2×2 \times 方块数（⩽70\leqslant 70），裸枚举上界 O(70n)O(70^{n})；剪枝后实测最大访问 2.5×1052.5\times10^{5} 个搜索节点（mayan10），10 组数据单组 0.19∼1.50.19 \sim 1.5 s，无剪枝对照组最坏 6.16×1066.16\times10^{6} 节点 / 36.8 s。
  • 空间：棋盘 O(35)O(35)，递归栈 O(n)O(n)，失败记忆集合 O(访问的不同局面数)O(\text{访问的不同局面数})，实测峰值约 17~19 MB（限制 128 MB）。

总结

  • 本题 = 规则模拟 + 状态空间搜索：模拟负责把一步移动映射成新局面（整体标记、掉落不判定、循环到稳定），搜索负责在恰好 nn 步的约束下找字典序最小路径。
  • 剪枝的合法性必须逐条论证，而不是「跑了没 WA 就行」：左移交换靠替换论证（等价转移中它字典序最大）、颜色计数靠不变量、记忆化靠后效性缺失（局面 + 剩余步数充分）、同色空转靠局面不变。任何删掉真解的剪枝都会把正解误判成 −1-1，这类错误比 WA 更难发现。
  • 「恰好 nn 步」与「字典序最小」两条输出语义分别落在叶子判空的时机与枚举循环的顺序上——把语义写进循环顺序，第一个解就是答案，省掉全解收集与比较。
  • Python 落地该题的胜负手是剪枝：同样算法不去重是 6×1066\times10^{6} 节点的 30 s 级别，剪完是 2.5×1052.5\times10^{5} 节点的秒级。

图示解析

下表用样例的第三步展示一次完整的「交换 → 双组同时消除 → 掉落 → 连锁消除 → 再掉落 → 再连锁」结算。每格是该列自下而上的方块串，× 表示该方块本轮被标记消除，· 表示空列：

阶段 x=0 x=1 x=2 x=3 x=4 观察重点
第 2 步后 1 2 1 2 1 4 3 4 2 3 3 4 起点
移动 (3,0,1) 交换 1 2 1 2 1 4 2 4 3 3 3 4 (3,0)(3,0) 的 3 与 (4,0)(4,0) 的 2 交换
第①轮标记 1 × 1 × 1 4 × 4 × × × 4 同时触发横 y=0y{=}0 的 x1∼x3x1{\sim}x3 三个 2 与竖 x=4x{=}4 的 y0∼y2y0{\sim}y2 三个 3
删除后掉落 1 1 1 4 4 4 x2 的 4 不动，x1/x2/x3 顶部落下
第②轮标记 × × × 4 4 4 掉落连锁出横 y=0y{=}0 的三个 1
删除后掉落 · · 4 4 4 只剩三个 4 压在底部
第③轮标记 · · × × × 横 y=0y{=}0 三个 4 全消
最终 · · · · · 第 3 步结算完恰好清空

这张表印证三点：同一轮里横、竖可以各自成组地同时消除（第①轮），这正是题面规则 2a/2b 要求整体标记的原因；每轮消除后必须先掉落再扫描，第②、③轮的三连都是掉落之后才出现的；一步移动可以触发多轮连锁，结算必须循环到稳定才算走完这一步。