[NOIP2011-提高] Mayan游戏

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

把棋盘压成五个列栈，按字典序做深度恰好为 n 的 DFS，配合逐层局面去重与无效移动剪枝，首个清空局面即字典序最小解。

OJ: roj

题目 ID: 3590

难度:提高

标签:搜索剪枝模拟python

创建: 2026-10-02 09:28

更新: 2026-10-10 11:30

形式化题目

棋盘是 5 列（ $x=0..4$ ）× 7 行（ $y=0..6$ ）的网格，方块不能悬空，因此每一列天然是一个自下而上的栈：底部到某一高度连续有方块，上面全空。给定初始局面（保证没有可以立即消除的三连）和要求通关的步数 $n$ ，做如下定义。

一次移动：选中有方块的格子 $(x,y)$ ，横向拖动一格，目标列 $x\pm1$ 必须仍在棋盘内。

目标 $(x\pm1,y)$ 有方块：两块原地交换位置；
目标为空：该块从原竖列中抽出（原列上方的方块补落一格），再从目标位置掉落，直到不悬空。

消除结算：只要某一横行或某一竖列上出现连续三个或更多同色方块，所有满足条件的方块同时被消除——一次移动可以同时触发多组，行列共享某个方块时也只消一次；随后上方方块掉落，掉落过程中不做检查，落定后若又出现三连就继续消，如此反复直到局面稳定。

目标：用恰好 $n$ 次移动清空整个棋盘；存在多组解时按 $x$ 第一、 $y$ 第二、方向 $1$ 优先于 $-1$ 取字典序最小的一组；不存在这样的移动序列则判定无解。

以题目样例（ $n=3$ ）展示三步移动与消除级联的完整过程，每列写成自下而上的颜色序列，空列记作"空"：

阶段	x=0	x=1	x=2	x=3	x=4
初始	1	2/1	2/3/4	3/1	2/4/3/4
第 1 步拖动 (2,1)→	1	2/1	2/1/4	3/3	2/4/3/4
第 2 步拖动 (3,1)→	1	2/1	2/1/4	3/4	2/3/3/4
第 3 步拖动 (3,0)→	1	2/1	2/1/4	2/4	3/3/3/4
第 3 步级联 1	1	1	1/4	4	4
第 3 步级联 2	空	空	4	4	4
第 3 步级联 3	空	空	空	空	空

这张表是后文所有规则的对照样本。前两步都只交换方块、没有凑出三连，说明一次移动不一定会触发消除；第 3 步把 $x=3$ 列的 $3$ 换到 $x=4$ 列底，于是竖列 $x=4$ 出现三个 $3$ ，而同一轮检查里 $y=0$ 行还有三个 $2$ （ $x=1..3$ ）——两组独立三连同时消除，这正是题面规则 a、b 的要求。掉落又依次凑出三个 $1$ 、三个 $4$ ，三轮级联后棋盘全空。

正解

思路

朴素做法：把移动当转移，全枚举。 每个局面的合法移动数是各列方块数之和的两倍（每块可左可右，边界列少一个方向），满盘 35 块时约 70 个分支；题面数据范围 $n \leqslant 5$ ，未剪枝的搜索树上界 $70^5 \approx 1.7\times10^9$ ，每个节点还要做一遍消除结算，直接枚举不可行。但深度只有 5 层这个事实同时说明：本题不需要更聪明的"数论式"结论，需要的是把模拟做对做快、把重复状态剪掉。

第一步：状态压成列栈。 因为方块不悬空， $5\times7$ 数组里的"空洞"信息是冗余的，整个局面只需 5 个自下而上的颜色序列。这样两种移动都能写成常数操作：

目标有方块 → 两列在高度 $y$ 处交换，两列交换后仍然实心，不需要先掉落；
目标为空 → 因为目标列实心且 $(x\pm1,y)$ 空，目标列高 $h\leqslant y$ ，方块不会被挡住，源列弹出 y 处 + 目标列尾部插入 一步同时完成"原列补落"和"落到目标列顶"。

消除则写成"标记 $\to$ 整组删除 $\to$ 循环"：横行用 None 补齐成定长 5 后扫连续段，竖列直接在栈上扫连续段，行列标记放进同一个集合再按列过滤——过滤本身就是掉落压实，外层循环到没有三连为止，正好实现"消除、掉落、再消除"的连锁。整个转移与棋盘尺寸同阶，是常数时间的纯函数，tuple 可哈希，局面可以直接进 set，连编码函数都省了。

第二步：让搜索顺序等于输出顺序。 题目要字典序最小的解，于是按 $x$ 升序 → $y$ 升序 → 方向先 $1$ 后 $-1$ 的顺序做深度优先搜索，走到第 $n$ 层时用"棋盘全空"判定成败：第一个成功的路径就是字典序最小解，因为所有字典序更小的前缀都会先被完整展开。相比之下 BFS 要按字典序排队所有路径，内存先爆；而 $n$ 由输入给定，也不需要迭代加深。

第三步：剪枝。

同层去重：同一层出现相同局面时，剩余步数相同、后续可行走法集合完全相同，先到的那次已经完整搜过（否则早已返回成功），后到的必然失败，直接跳过。注意 seen 必须按层分桶——判据是"恰好第 $n$ 步清空"，第 $d$ 层的子问题要求"再走 $n-d$ 步"，不同层的同局面不是同一个子问题，用全局 set 合并会丢解。
无效移动：目标出界不合法；目标方块与源方块同色时交换后局面完全不变，直接跳过。

单步结算与搜索主循环的流程如下：

flowchart TD
    A["search(s, d)：第 d 步的局面 s"] --> B{"d == n ?"}
    B -->|是| C{"s 已全空 ?"}
    C -->|是| D["沿途回溯记录移动，返回成功"]
    C -->|否| E["失败回溯"]
    B -->|否| F{"s 已在第 d 层展开过 ?"}
    F -->|是| E
    F -->|否| G["登记 s 进 seen[d]"]
    G --> H["按 x、y、方向(先 1 后 -1) 枚举移动"]
    H --> I["slide：拖动 + 消除级联"]
    I --> J["search(新局面, d+1)"]
    J -->|成功| D
    J -->|失败| H

流程图强调两件事：成功判定只发生在 d == n 的叶子上；seen[d] 的查询发生在枚举移动之前，所以整棵重复子树在入口处就被剪断，而不是展开后再发现重复。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int W = 5, Hh = 7;
typedef vector<vector<int> > Board;

string encode_board(const Board &cols) {
    string s;
    for (int x = 0; x < W; x++) {
        s.push_back('|');
        for (int y = 0; y < (int)cols[x].size(); y++) {
            s += to_string(cols[x][y]); s.push_back(',');
        }
    }
    return s;
}

bool clear_once(const Board &cols, Board &out) {
    bool mark[W][Hh]; memset(mark, 0, sizeof(mark));
    int rows[Hh][W];
    for (int y = 0; y < Hh; y++) for (int x = 0; x < W; x++) rows[y][x] = y < (int)cols[x].size() ? cols[x][y] : -1;
    for (int y = 0; y < Hh; y++) {
        int x = 0;
        while (x < W) {
            int k = x;
            while (k + 1 < W && rows[y][x] != -1 && rows[y][k + 1] == rows[y][x]) k++;
            if (k - x >= 2) for (int i = x; i <= k; i++) mark[i][y] = true;
            x = k + 1;
        }
    }
    for (int x = 0; x < W; x++) {
        int y = 0;
        while (y < (int)cols[x].size()) {
            int k = y;
            while (k + 1 < (int)cols[x].size() && cols[x][k + 1] == cols[x][y]) k++;
            if (k - y >= 2) for (int i = y; i <= k; i++) mark[x][i] = true;
            y = k + 1;
        }
    }
    bool any = false;
    out.assign(W, vector<int>());
    for (int x = 0; x < W; x++) for (int y = 0; y < (int)cols[x].size(); y++) {
        if (mark[x][y]) any = true; else out[x].push_back(cols[x][y]);
    }
    return any;
}

bool slide_board(const Board &cols, int x, int y, int d, Board &res) {
    int x2 = x + d;
    if (x2 < 0 || x2 >= W || y >= (int)cols[x].size()) return false;
    Board moved = cols;
    if (y < (int)moved[x2].size()) {
        if (moved[x][y] == moved[x2][y]) return false;
        swap(moved[x][y], moved[x2][y]);
    } else {
        int color = moved[x][y];
        moved[x].erase(moved[x].begin() + y);
        moved[x2].push_back(color);
    }
    Board nxt = moved, tmp;
    while (clear_once(nxt, tmp)) nxt = tmp;
    res = nxt;
    return true;
}

bool search_board(const Board &cols, int depth, int limit, vector<set<string> > &seen, vector<array<int,3> > &path) {
    if (depth == limit) {
        for (int x = 0; x < W; x++) if (!cols[x].empty()) return false;
        return true;
    }
    string key = encode_board(cols);
    if (seen[depth].count(key)) return false;
    seen[depth].insert(key);
    for (int x = 0; x < W; x++) for (int y = 0; y < (int)cols[x].size(); y++) {
        int dirs[2] = {1, -1};
        for (int z = 0; z < 2; z++) {
            Board nxt;
            if (slide_board(cols, x, y, dirs[z], nxt) && search_board(nxt, depth + 1, limit, seen, path)) {
                path.push_back({x, y, dirs[z]});
                return true;
            }
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int steps; if (!(cin >> steps)) return 0;
    Board columns(W);
    for (int x = 0; x < W; x++) { int color; while (cin >> color && color != 0) columns[x].push_back(color); }
    vector<set<string> > seen(steps);
    vector<array<int,3> > path;
    if (search_board(columns, 0, steps, seen, path)) {
        for (int i = (int)path.size() - 1; i >= 0; i--) cout << path[i][0] << ' ' << path[i][1] << ' ' << path[i][2] << '\n';
        if (path.empty()) cout << '\n';
    } else cout << -1 << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 09:42
# update_at: 2026-10-02 09:42

import sys

W = 5  # 棋盘横向列数，x ∈ [0, 4]
H = 7  # 棋盘纵向行数，y ∈ [0, 6]

# 局面编码：5 元组，第 x 个元素是第 x 列的颜色序列（从下往上），空格子就是列比 y 短。


def clear_once(cols):
    """消去一次：横行或竖列出现连续三块同色就整组删掉，返回掉落压实后的新局面；无三连返回 None。"""
    mark: set[tuple[int, int]] = set()
    # 每行先补成定长 5，空位用 None 占据（None 不参与同色比较）
    rows = [[col[y] if y < len(col) else None for col in cols] for y in range(H)]

    for y, row in enumerate(rows):
        x = 0
        while x < W:
            k = x
            while k + 1 < W and row[x] is not None and row[k + 1] == row[x]:
                k += 1
            if k - x >= 2:  # 连续段长度 ≥ 3
                mark.update((i, y) for i in range(x, k + 1))
            x = k + 1

    for x, col in enumerate(cols):
        y = 0
        while y < len(col):
            k = y
            while k + 1 < len(col) and col[k + 1] == col[y]:
                k += 1
            if k - y >= 2:
                mark.update((x, i) for i in range(y, k + 1))
            y = k + 1

    if not mark:
        return None
    # 行、列的三连在同一轮里一起删：按列过滤即让被删格上方的方块掉落
    return tuple(
        tuple(color for i, color in enumerate(col) if (x, i) not in mark)
        for x, col in enumerate(cols)
    )


def slide(cols, x: int, y: int, d: int):
    """把 (x, y) 的方块横向拖 d 格并结算消除连锁；不合法或局面不变时返回 None。"""
    x2 = x + d
    if x2 < 0 or x2 >= W or y >= len(cols[x]):  # 出界或该格没方块
        return None

    src, dst = list(cols[x]), list(cols[x2])
    if y < len(dst):
        if src[y] == dst[y]:  # 换的是同色方块，局面完全不变，属于无效移动
            return None
        src[y], dst[y] = dst[y], src[y]  # 目标位置有方块：原地交换
    else:
        dst.append(src.pop(y))  # 目标为空：从竖列抽出，落到目标列顶（目标列必不高于 y）

    moved = list(cols)
    moved[x], moved[x2] = tuple(src), tuple(dst)
    nxt = tuple(moved)
    while (changed := clear_once(nxt)) is not None:  # 消除后掉落可能再次触发消除
        nxt = changed
    return nxt


def search(cols, depth: int, limit: int, seen: list[set], path: list) -> bool:
    """按字典序 DFS：从第 depth 步的局面出发，恰好用满 limit 步清空棋盘；找到即把路径倒序留在 path。"""
    if depth == limit:
        return not any(cols)  # 只有走满全部步数时清空才算解
    if cols in seen[depth]:  # 同一层的相同局面：先前那次已经搜过全部续接，直接剪掉
        return False
    seen[depth].add(cols)
    for x in range(W):
        for y in range(len(cols[x])):  # y 由小到大，配合外层 x 即字典序
            for d in (1, -1):  # 同一格先向右（1 优先于 -1）
                nxt = slide(cols, x, y, d)
                if nxt is not None and search(nxt, depth + 1, limit, seen, path):
                    path.append((x, y, d))  # 回溯时记录，最后反转成正序
                    return True
    return False


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    steps = next(data)

    columns = []
    for _ in range(W):
        column = []
        while (color := next(data)) != 0:  # 每列以 0 结尾，自下向上
            column.append(color)
        columns.append(tuple(column))

    seen: list[set] = [set() for _ in range(steps)]
    path: list[tuple[int, int, int]] = []
    if search(tuple(columns), 0, steps, seen, path):
        print('\n'.join(f'{x} {y} {d}' for x, y, d in reversed(path)))
    else:
        print(-1)


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：设按层去重后实际展开的局面总数为 $S$ ，方块总数 $B \leqslant 35$ ，则每个局面最多枚举 $2B$ 个移动、每次结算只做固定 $5\times7$ 的扫描（常数 $C$ ），总计 $O(S \cdot B \cdot C)$ ，即关于 $S$ 线性；未剪枝的搜索树上界为 $(2B)^n$ ， $n \leqslant 5$ 。
空间复杂度： $O(S \cdot B)$ ，保存各层已展开局面的集合；递归深度 $n \leqslant 5$ ，调用栈 $O(n)$ 。

总结

本题是"小深度状态空间搜索 + 确定性模拟"：难点不在算法思想，而在把交换、抽出、同时消除、连锁掉落这几条规则无遗漏地落成一个纯函数转移。
局面表示选对了，实现就短：列栈让"抽出 + 落地"变成一次 pop + 一次 append，让"掉落压实"变成一次过滤，让状态去重变成一个 set。
要字典序最小的解，就把枚举顺序写成字典序，第一个成功解无需比较。
去重必须分层：同层同局面才等价，跨层剩余步数不同，合并会丢解。
本解法复杂度与正解同阶；实测 10 组真实数据全部一致，最慢约 2.1s（本地限时 20s），Python 侧存在 OJ 限时风险但算法本身没有退化成暴力。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4状态 = 5 个列栈（可哈希 tuple，35 格常数转移）
|- 单步结算：拖动(交换/抽出) → 同时标记消除 → 掉落压实 → 连锁
|- 搜索顺序：按 x、y、方向(先右后左) 的字典序 DFS，深度恰好 n
   `- 剪枝：同层去重 + 无效移动 → 首个全空局面即最小解，全失败则 -1

先看第一行的建模结论：它决定了后面所有操作都是常数代价；再沿两条分支检查——模拟保证"转移正确"，搜索顺序保证"答案字典序最小"，剪枝只砍掉与已展开子树完全同构的重复状态，不丢解。

题目描述

Mayan puzzle是最近流行起来的一个游戏。游戏界面是一个$ 7$ 行$ \times 5 $列的棋盘，上面堆放着一些方块，方块不能悬空堆放，即方块必须放在最下面一行，或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块，消除方块的规则如下：

1 、每步移动可以且仅可以沿横向（即向左或向右）拖动某一方块一格：当拖动这一方块时，如果拖动后到达的位置（以下称目标位置）也有方块，那么这两个方块将交换位置（参见输入输出样例说明中的图$6 $到图 $7$ ）；如果目标位置上没有方块，那么被拖动的方块将从原来的竖列中抽出，并从目标位置上掉落（直到不悬空，参见下面图1 和图2）；

2 、任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则它们将立即被消除（参见图1 到图3）。

注意：

a) 如果同时有多组方块满足消除条件，几组方块会同时被消除（例如下面图 $4$ ，三个颜色为 $1$ 的方块和三个颜色为 $2$ 的方块会同时被消除，最后剩下一个颜色为$ 2 $的方块）。

b) 当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除（例如下面图5 所示的情形，5 个方块会同时被消除）。

3 、方块消除之后，消除位置之上的方块将掉落，掉落后可能会引起新的方块消除。注意：掉落的过程中将不会有方块的消除。

上面图1 到图 3 给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为（0, 0 ），将位于（3, 3 ）的方块向左移动之后，游戏界面从图 1 变成图 2 所示的状态，此时在一竖列上有连续三块颜色为4 的方块，满足消除条件，消除连续3 块颜色为4 的方块后，上方的颜色为3 的方块掉落，形成图 3 所示的局面。

输入输出格式

输入格式：

共 6 行。

第一行为一个正整数$n $，表示要求游戏通关的步数。

接下来的 $5 $行，描述$ 7 \times 5$ 的游戏界面。每行若干个整数，每两个整数之间用一个空格隔开，每行以一个 $0$ 结束，自下向上表示每竖列方块的颜色编号（颜色不多于 $10$ 种，从$1 $开始顺序编号，相同数字表示相同颜色）。

输入数据保证初始棋盘中没有可以消除的方块。

输出格式：

如果有解决方案，输出 $n$ 行，每行包含 $3$ 个整数 $x,y,g$ ，表示一次移动，每两个整数之间用一个空格隔开，其中 $(x ,y)$ 表示要移动的方块的坐标， $g$ 表示移动的方向， $1$ 表示向右移动， $-1$ 表示向左移动。注意：多组解时，按照 $x$ 为第一关健字， $y$ 为第二关健字， $1$ 优先于 $-1$ ，给出一组字典序最小的解。游戏界面左下角的坐标为 $(0 ,0)$ 。

如果没有解决方案，输出一行，包含一个整数 $-1$ 。

输入输出样例

输入样例#1：

3 1 0 2 1 0 2 3 4 0 3 1 0 2 4 3 4 0

输出样例#1：

2 1 1 3 1 1 3 0 1

说明

【输入输出样例说明】

按箭头方向的顺序分别为图 $6$ 到图 $11$

样例输入的游戏局面如上面第一个图片所示，依次移动的三步是： $(2 ,1 )$ 处的方格向右移动， $(3,1)$ 处的方格向右移动， $(3,0)$ 处的方格向右移动，最后可以将棋盘上所有方块消除。

【数据范围】

对于 $30\%$ 的数据，初始棋盘上的方块都在棋盘的最下面一行；

对于 $100\%$ 的数据， $0 < n≤5$ 。

noip2011提高组day1第3题