题解：P1312 [NOIP2011 提高组] Mayan 游戏

lihongru · 2025-01-24 15:05:15 · 题解

题目分析

本题没有什么特别的办法，只能尝试每一个步骤的走法。说到尝试，就一定是搜索了。不过本题的搜索比较复杂，夹杂了模拟。我认为本题难度主要在代码上。

为了方便，我们将本题的编号起点 (0, 0) 调整为 (1, 1)，并在最后输出时 -1。

移动-move 函数

先不管如何搜索操作步骤。对于每一次移动块，先要交换块，然后进行删除，删除后出现新的空，需要进行下落，下落后又有新的块……由此，我们可以先来实现一个移动的函数。

void move(int x, int y, int k){
    swap(mp[x][y], mp[x+k][y]); // 1交换
    down(); // 2下落
    while (remove()) down(); // 3判定并继续下落
}

其中 remove 表示消除（返回值为是否进行了至少一组的消除），down 表示下落。

下落-down 函数

接下来我们就可以开始完成这两个函数了。先来看 down 函数。

首先我们知道，下落不会引起列交换。所以我们对于 5 列，分别处理。快速的办法就是新建一个数组，将所有不为 0 的块拷贝进去（不留空白），再重新拷贝出来。例如一列 0010230，进入数组后 1230000，再回到这一列就变成了 1230000，比朴素向下找方便。

void down(){
    for (int i = 1; i <= 5; i++){
        int b[10] = {}, cnt = 0; // 此处将b数组清0了
        for (int j = 1; j <= 7; j++){
            if (mp[i][j]) b[++cnt] = mp[i][j]; // 加入新数组
        }
        for (int j = 1; j <= 7; j++){
            mp[i][j] = b[j]; // 移回原数组，并覆盖多余部分
        }
    }
}

移除-remove 函数

接下来就是 remove 函数。这是比较复杂的一个函数。因为可能出现题目描述中“共享方块”的问题，我们不能直接修改原数组。这个时候我们就需要一个辅助数组了。

一旦找到某个块可以作为消除块的中间，标记到辅助数组。最终把辅助数组中的标记和原数组中的被标记位置一同清空，并检查是否消除了块。一定注意，空白不能作为一个“空白块”的中间位置，遇到空白要跳过，否则可能会出现死循环。

bool remove(){
    for (int i = 1; i <= 5; i++){
        for (int j = 1; j <= 7; j++){
            if (!mp[i][j]) continue; // 空白块要跳过
            if (mp[i-1][j] == mp[i][j] && mp[i+1][j] == mp[i][j])
                v[i-1][j] = v[i][j] = v[i+1][j] = 1; // 标记横向块
            if (mp[i][j-1] == mp[i][j] && mp[i][j+1] == mp[i][j])
                v[i][j-1] = v[i][j] = v[i][j+1] = 1; // 标记纵向块
        }
    }
    bool ret = false; // 寻找是否消除
    for (int i = 1; i <= 5; i++){
        for (int j = 1; j <= 7; j++){
            if (v[i][j]) {
                mp[i][j] = v[i][j] = 0;
                ret = true;
            }
        }
    }
    return ret;
}

三个函数都完成了，接下来就可以进入重点的搜索部分了。

搜索-dfs 函数

要说搜索，我们可以枚举 5 \times 7 个块判断消除，这是完全没有问题的。最坑的地方就是回溯，因为无法还原出原状态。

当然，解决办法也很简单——再加辅助数组。在找之前，先把原数据复制过来，每次回溯再复制回去。

另外，除了剪枝，我们还得使用数组记录答案，最终还需要一个判断是否完成的函数 check，具体怎么写见下一部分。

void dfs(int x){
    if (flag) return ;
    if (check()){
        for (int i = 1; i <= n; i++){
            cout << ans[i][1] << " " << ans[i][2] << " " << ans[i][3] << endl;
        }
        flag = true;
        return ;
    }
    if (x > n) return ;
    int tmp[10][10];
    memcpy(tmp, mp, sizeof tmp);
    for (int i = 1; i <= 5; i++){
        for (int j = 1; j <= 7; j++){
            if (!mp[i][j]) break;
            if (i < 5){
                ans[x][1] = i - 1;
                ans[x][2] = j - 1;
                ans[x][3] = 1;
                move(i, j, 1); dfs(x+1);
                memcpy(mp, tmp, sizeof mp);
            }
            if (i > 1 && !mp[i-1][j]){
                ans[x][1] = i - 1;
                ans[x][2] = j - 1;
                ans[x][3] = -1;
                move(i, j, -1); dfs(x+1);
                memcpy(mp, tmp, sizeof mp);
            }
        }
    }
}

注意：1 优先于 -1，一定要先搜索向右移动。向右移动，右边只要不为空，即可移动。向左移动需要注意不能移到空白处。

检查-check 函数

非常简单，由于我们可以保证在执行 check 函数时，数组状态完全合法，所以只找第一横行是否有块即可。

bool check(){
    for (int i = 1; i <= 5; i++){
        if (mp[i][1]) return false;
    }
    return true;
}

关于 Hack 数据

Hack 数据仅需 1 步即可完成，但它的输入 n 大于 1。我的代码最开始被 Hack 了，是因为判断向右的时候多加了不相同才换的条件。对于这种情况，需要通过“无效交换”“拖延”步数，所以不能加“不相同才换”的条件。

题目总结与参考代码

本题主要难度是如何进行搜索，以及搜索过程中的模拟。调代码的难度也是比较大的，可以通过加辅助输出或者 return 来调错。

#include <bits/stdc++.h>
using namespace std;

int n, mp[10][10], v[10][10], ans[10][5];
bool flag;

void down(){
    for (int i = 1; i <= 5; i++){
        int b[10] = {}, cnt = 0;
        for (int j = 1; j <= 7; j++){
            if (mp[i][j]) b[++cnt] = mp[i][j];
        }
        for (int j = 1; j <= 7; j++){
            mp[i][j] = b[j];
        }
    }
}

bool remove(){
    for (int i = 1; i <= 5; i++){
        for (int j = 1; j <= 7; j++){
            if (!mp[i][j]) continue;
            if (mp[i-1][j] == mp[i][j] && mp[i+1][j] == mp[i][j])
                v[i-1][j] = v[i][j] = v[i+1][j] = 1;
            if (mp[i][j-1] == mp[i][j] && mp[i][j+1] == mp[i][j])
                v[i][j-1] = v[i][j] = v[i][j+1] = 1;
        }
    }
    bool ret = false;
    for (int i = 1; i <= 5; i++){
        for (int j = 1; j <= 7; j++){
            if (v[i][j]) {
                mp[i][j] = v[i][j] = 0;
                ret = true;
            }
        }
    }
    return ret;
}

bool check(){
    for (int i = 1; i <= 5; i++){
        if (mp[i][1]) return false;
    }
    return true;
}

void move(int x, int y, int k){
    swap(mp[x][y], mp[x+k][y]);
    down();
    while (remove()) down();
}

void dfs(int x){
    if (flag) return ;
    if (check()){
        for (int i = 1; i <= n; i++){
            cout << ans[i][1] << " " << ans[i][2] << " " << ans[i][3] << endl;
        }
        flag = true;
        return ;
    }
    if (x > n) return ;
    int tmp[10][10];
    memcpy(tmp, mp, sizeof tmp);
    for (int i = 1; i <= 5; i++){
        for (int j = 1; j <= 7; j++){
            if (!mp[i][j]) break;
            if (i < 5){
                ans[x][1] = i - 1;
                ans[x][2] = j - 1;
                ans[x][3] = 1;
                move(i, j, 1); dfs(x+1);
                memcpy(mp, tmp, sizeof mp);
            }
            if (i > 1 && !mp[i-1][j]){
                ans[x][1] = i - 1;
                ans[x][2] = j - 1;
                ans[x][3] = -1;
                move(i, j, -1); dfs(x+1);
                memcpy(mp, tmp, sizeof mp);
            }
        }
    }
}

int main(){
    cin >> n;
    for (int i = 1; i <= 5; i++){
        int p = 0, x; cin >> x;
        while (x) {
            mp[i][++p] = x;
            cin >> x;
        }
    }
    dfs(1);
    if (!flag) 
        cout << -1 << endl;
    return 0;
}