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

furina_yyds · 2025-01-16 21:09:42 · 题解

思路

本题为 DFS。

创建三个函数，实现三个模块。

• down： 实现方块的下落。
• del： 实现方块的消除。
• dfs： 实现主要生成函数。

对于左移部分，如果左边为空才需要左移，否则，这个方块会被其他方块右移得到相同的效果。

代码

#include<iostream>
#include<cstring>
using namespace std;
struct Node{
    int x, y, op;
};
Node b[10]; 
int a[10][10];
int n;
inline void down(){
    for (int i = 1; i <= 5; i++){
        int sz = 0;
        for (int j = 1; j <= 7; j++)
            if (a[i][j]) a[i][++sz] = a[i][j];
        for (int j = sz + 1; j <= 7; j++) a[i][j] = 0;
    }
}
inline bool del(){
    int t[10][10];
    memcpy(t, a, sizeof(a));
    bool flag = false;
    for (int i = 1; i <= 5; i++){
        for (int j = 1; j <= 7; j++){
            if (!a[i][j]) continue;
            if (a[i][j] == a[i - 1][j] && a[i][j] == a[i + 1][j]){
                t[i][j] = t[i - 1][j] = t[i + 1][j] = 0;
                flag = true;
            }
            if (a[i][j] == a[i][j - 1] && a[i][j] == a[i][j + 1]){
                t[i][j] = t[i][j - 1] = t[i][j + 1] = 0;
                flag = true;
            }
        }
    }
    memcpy(a, t, sizeof(t));
    return flag;
}
inline void dfs(int step){
    down();
    while (del()) down();
    if (step > n){
        for (int i = 1; i <= 5; i++)
            if (a[i][1]) return;
        for (int i = 1; i <= n; i++)
            cout << b[i].x - 1 << " " << b[i].y - 1 << " " << b[i].op << endl;
        exit(0);
    }
    int t[10][10];
    memcpy(t, a, sizeof(a));
    for (int i = 1; i <= 5; i++){
        for (int j = 1; j <= 7; j++){
            if (a[i][j] == 0) break;
            if (i < 5){
                swap(a[i][j], a[i + 1][j]);
                b[step] = {i, j, 1};
                dfs(step + 1);
                memcpy(a, t, sizeof(t));
            }
            if (i > 1 && a[i - 1][j] == 0){
                swap(a[i][j], a[i - 1][j]);
                b[step] = {i, j, -1};
                dfs(step + 1);
                memcpy(a, t, sizeof(t));
            }
        }
    }
}
int main(){
    cin >> n;
    for (int i = 1; i <= 5; i++){
        for (int j = 1; j <= 8; j++){
            int x;
            cin >> x;
            if (x == 0) break;
            a[i][j] = x;
        }
    }   
    dfs(1);
    cout << -1 << endl;
    return 0;
}

AC 记录