[NOIP2014-提高] 寻找道路

形式化题目

非常重要：本题的实际数据内容为经典的《Mayan 游戏》（NOIP2011 提高组 D1T3），而前台题目描述被错误地替换成了《寻找道路》（NOIP2014 提高组 D2T2）。所有代码实现和本题解均以真实数据（Mayan 游戏）为准。

游戏在一个 $5 \times 7$ 的网格上进行，左下角坐标为 $(0, 0)$ ，右上角坐标为 $(4, 6)$ 。每个格子可能为空，也可能有一个特定颜色的方块（用 $1 \sim 10$ 之间的整数表示）。你可以执行 $n$ 次操作。每次操作可以将某个方块与其左边或右边的相邻格子交换（如果相邻格子为空则相当于直接平移过去）。如果下方悬空，方块会一直下落直到碰到其他方块或底部。当下落静止后，如果存在横向或纵向连续 $\ge 3$ 个颜色相同的方块，它们会被同时消除。消除后如果上方有方块，它们又会下落并可能引发连锁消除。给定初始网格，要求输出恰好进行 $n$ 次操作，使网格中所有方块都被消除的移动方案。如果不存在方案，输出 -1。输出格式要求：如果存在方案，输出 $n$ 行，每行三个整数 $x, y, g$ ，表示将坐标为 $(x, y)$ 的方块向右移动（ $g=1$ ）或向左移动（ $g=-1$ ）。如果有多种方案，输出字典序最小的一组。

正解

思路

这是一个典型的带有复杂状态转移的搜索题，我们需要使用深度优先搜索（DFS）来枚举每一步操作，并配合充分的剪枝来通过。

在每一步枚举中，我们要模拟：

交换：将选中的方块向左或向右交换。
下落与消除：写一个模拟函数，循环执行“下落 - 消除”直到网格稳定不再发生任何消除。

为了保证能在时间限制内得出结果并输出字典序最小的答案，需要以下优化与剪枝：

字典序优先：枚举坐标时外层循环为 $x$ ，内层循环为 $y$ （先选小的横坐标和小的纵坐标）；对于同一个方块，优先尝试向右移动（即优先枚举 $g=1$ 再枚举 $g=-1$ ）。
等效操作剪枝：如果一个方块向左移动，且左边的格子也有方块，那么这个动作等效于左边的方块向右移动。但后者在字典序中排在前面！因此，我们规定：当且仅当左边为空时，才允许方块向左移动。
同色交换剪枝：如果一个方块向右移动，且右边格子是同色方块，交换是毫无意义的，可以直接跳过。
不可消除剪枝：在任意时刻，统计网格中各种颜色方块的数量。如果存在某一种颜色的方块数量为 $1$ 个或 $2$ 个，它们永远无法凑齐 $3$ 个来被消除，此时当前状态必然无解，可以直接 return false 回溯。

代码

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
109import sys

def fall(g):
    for x in range(5):
        ptr = 0
        for y in range(7):
            if g[x][y] != 0:
                val = g[x][y]
                g[x][y] = 0
                g[x][ptr] = val
                ptr += 1

def clear_blocks(g):
    to_clear = [[False]*7 for _ in range(5)]
    any_clear = False
    for x in range(5):
        for y in range(7):
            c = g[x][y]
            if c != 0:
                if x + 2 < 5 and g[x+1][y] == c and g[x+2][y] == c:
                    to_clear[x][y] = to_clear[x+1][y] = to_clear[x+2][y] = True
                    any_clear = True
                if y + 2 < 7 and g[x][y+1] == c and g[x][y+2] == c:
                    to_clear[x][y] = to_clear[x][y+1] = to_clear[x][y+2] = True
                    any_clear = True
    if not any_clear:
        return False
    for x in range(5):
        for y in range(7):
            if to_clear[x][y]:
                g[x][y] = 0
    return True

def process(g):
    fall(g)
    while clear_blocks(g):
        fall(g)

def solve():
    sys.setrecursionlimit(200000)
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    n = int(input_data[0])
    g = [[0]*7 for _ in range(5)]
    idx = 1
    for x in range(5):
        y = 0
        while idx < len(input_data):
            val = int(input_data[idx])
            idx += 1
            if val == 0:
                break
            g[x][y] = val
            y += 1
            
    ans = []
    
    def dfs(step, current_g):
        if step == n:
            for x in range(5):
                if current_g[x][0] != 0:
                    return False
            return True
            
        cnt = [0] * 11
        for x in range(5):
            for y in range(7):
                if current_g[x][y] != 0:
                    cnt[current_g[x][y]] += 1
        for i in range(1, 11):
            if cnt[i] == 1 or cnt[i] == 2:
                return False
                
        for x in range(5):
            for y in range(7):
                if current_g[x][y] == 0:
                    continue
                    
                # Move right
                if x + 1 < 5 and current_g[x][y] != current_g[x+1][y]:
                    next_g = [col[:] for col in current_g]
                    next_g[x][y], next_g[x+1][y] = next_g[x+1][y], next_g[x][y]
                    process(next_g)
                    ans.append((x, y, 1))
                    if dfs(step + 1, next_g):
                        return True
                    ans.pop()
                    
                # Move left
                if x - 1 >= 0 and current_g[x-1][y] == 0:
                    next_g = [col[:] for col in current_g]
                    next_g[x][y], next_g[x-1][y] = next_g[x-1][y], next_g[x][y]
                    process(next_g)
                    ans.append((x, y, -1))
                    if dfs(step + 1, next_g):
                        return True
                    ans.pop()
                    
        return False
        
    if dfs(0, g):
        for move in ans:
            print(f"{move[0]} {move[1]} {move[2]}")
    else:
        print("-1")

if __name__ == '__main__':
    solve()

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int n;
int initial_grid[5][7];

struct Move {
    int x, y, g;
} ans[10];

// 方块下落逻辑：让每一列悬空的方块落到底部
void fall(int g[5][7]) {
    for (int x = 0; x < 5; ++x) {
        int ptr = 0;
        for (int y = 0; y < 7; ++y) {
            if (g[x][y] != 0) {
                g[x][ptr++] = g[x][y];
            }
        }
        for (int y = ptr; y < 7; ++y) {
            g[x][y] = 0;
        }
    }
}

// 消除连续 >= 3 的同色方块
bool clear_blocks(int g[5][7]) {
    bool to_clear[5][7] = {false};
    bool any_clear = false;
    for (int x = 0; x < 5; ++x) {
        for (int y = 0; y < 7; ++y) {
            if (g[x][y] != 0) {
                int val = g[x][y];
                // 水平检测
                if (x - 1 >= 0 && x + 1 < 5 && g[x-1][y] == val && g[x+1][y] == val) {
                    to_clear[x-1][y] = to_clear[x][y] = to_clear[x+1][y] = true;
                    any_clear = true;
                }
                // 垂直检测
                if (y - 1 >= 0 && y + 1 < 7 && g[x][y-1] == val && g[x][y+1] == val) {
                    to_clear[x][y-1] = to_clear[x][y] = to_clear[x][y+1] = true;
                    any_clear = true;
                }
            }
        }
    }
    if (!any_clear) return false;
    for (int x = 0; x < 5; ++x) {
        for (int y = 0; y < 7; ++y) {
            if (to_clear[x][y]) {
                g[x][y] = 0;
            }
        }
    }
    return true;
}

// 掉落与消除循环，直到稳定
void process(int g[5][7]) {
    fall(g);
    while (clear_blocks(g)) {
        fall(g);
    }
}

// 深度优先搜索
bool dfs(int step, int g[5][7]) {
    if (step == n) {
        // 检查是否全部消除完
        for (int x = 0; x < 5; ++x) {
            if (g[x][0] != 0) return false;
        }
        return true;
    }
    
    // 剪枝1：如果某种颜色的方块只剩 1 个或 2 个，绝对不可能消除，直接剪枝
    int cnt[11] = {0};
    for (int x = 0; x < 5; ++x) {
        for (int y = 0; y < 7; ++y) {
            if (g[x][y] != 0) {
                cnt[g[x][y]]++;
            }
        }
    }
    for (int i = 1; i <= 10; ++i) {
        if (cnt[i] == 1 || cnt[i] == 2) return false;
    }
    
    int next_g[5][7];
    for (int x = 0; x < 5; ++x) {
        for (int y = 0; y < 7; ++y) {
            if (g[x][y] == 0) continue;
            
            // 剪枝及移动优先级1：优先向右移动 (字典序要求 x 小、g=1 优先)
            if (x + 1 < 5) {
                if (g[x][y] != g[x+1][y]) { // 剪枝：颜色相同交换无意义
                    memcpy(next_g, g, sizeof(next_g));
                    swap(next_g[x][y], next_g[x+1][y]);
                    process(next_g);
                    ans[step] = {x, y, 1};
                    if (dfs(step + 1, next_g)) return true;
                }
            }
            
            // 剪枝及移动优先级2：向左移动 (当且仅当左侧为空时才移动)
            // 如果左侧有方块，将其向左移动等效于将其左侧的方块向右移动，而后者字典序更优！
            if (x - 1 >= 0 && g[x-1][y] == 0) {
                memcpy(next_g, g, sizeof(next_g));
                swap(next_g[x][y], next_g[x-1][y]);
                process(next_g);
                ans[step] = {x, y, -1};
                if (dfs(step + 1, next_g)) return true;
            }
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    if (!(cin >> n)) return 0;
    
    memset(initial_grid, 0, sizeof(initial_grid));
    for (int x = 0; x < 5; ++x) {
        int y = 0;
        int val;
        while (cin >> val && val != 0) {
            initial_grid[x][y++] = val;
        }
    }
    
    if (dfs(0, initial_grid)) {
        for (int i = 0; i < n; ++i) {
            cout << ans[i].x << " " << ans[i].y << " " << ans[i].g << "\n";
        }
    } else {
        cout << "-1\n";
    }
    
    return 0;
}

复杂度

时间复杂度：最坏情况下要搜索 $5 \times 7 \times 2 = 70$ 个可能的操作，深度为 $n \le 5$ 。理论上的搜索树大小约为 $O(70^n)$ 。但由于大量剪枝（特别是等效操作剪枝和同色剪枝），实际搜索树的规模非常小，完全可以通过。单次状态转移需要模拟消除，花费常数级别的时间，总时间复杂度在剪枝后能稳定通过。
空间复杂度：由于 DFS 深度最大为 $5$ ，每层需要一个 $5 \times 7$ 的二维数组记录当前状态。空间复杂度为 $O(n)$ ，远小于内存限制。

总结

坑点一：题面与数据严重不符。 题面是《寻找道路》，但数据是《Mayan 游戏》。我们必须完全根据数据的真实意图进行解题。
坑点二：字典序的正确处理和等效操作的去除。 如果不加限制地向左和向右枚举，不仅会导致死循环/冗余搜索，还会破坏字典序的判定。左移只有在“目标位置为空”时才有独立意义。
坑点三：连锁消除的模拟。 方块被标记消除后必须统一清空，然后再执行掉落，掉落后还要再次检查是否有新的消除，必须使用 while 循环直至没有方块被标记为止。

[NOIP2014-提高] 寻找道路

目录

形式化题目

正解

思路

代码

复杂度

总结