题解 | mayan游戏题解

搜索+大模拟。不过思路明确后还是可以写的。
搜索树每一层代表移动了几次。每次枚举移动哪个位置，以及可以写个两个函数，一个来处理每一列的下降（移动或消除），第二个将每次可消的方块标记出来，然后再次下降（注意一次移动可能会导致多次消除，所以得重复判断），以及每次要记得把原数组copy了以便回溯。
复杂度上界应该是35^7。但是跑不满（中间跑出解了）。

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

bool vis[10][10];
int st[10][4], top = 0;
int a[10][10];
int n;
bool flag = 0;

void down(int x) {
    int zero = 0;
    for(int i = 0; i < 7; ++i) {
        if(a[x][i]) {
            if(!zero) continue;
            a[x][i - zero] = a[x][i];
            a[x][i] = 0;
        } else ++zero;
    }
}

bool clear() {
    bool f = 0;
    for(int i = 0; i < 5; ++i) for(int j = 0; j < 7; ++j) vis[i][j] = 0;
    for(int i = 0; i < 5; ++i) {
        for(int j = 0; j < 7; ++j) {
            if(i + 2 < 5) {
                if(a[i][j] && a[i][j] == a[i + 1][j] && a[i][j] == a[i + 2][j]) {
                    f = 1; vis[i][j] = vis[i + 1][j] = vis[i + 2][j] = 1;
                } 
            }
            if(j + 2 < 7) {
                if(a[i][j] && a[i][j] == a[i][j + 1] && a[i][j] == a[i][j + 2]) {
                    f = 1; vis[i][j] = vis[i][j + 1] = vis[i][j + 2] = 1;
                }
            }
        }
    }
    if(!f) return 0;
    for(int i = 0; i < 5; ++i) for(int j = 0; j < 7; ++j) if(vis[i][j]) a[i][j] = 0, f = 1;
    for(int i = 0; i < 5; ++i) down(i);
    return 1;
}

void dfs(int x) {
    if(x == n + 1) {
        for(int i = 0; i < 5; ++i) for(int j = 0; j < 7; ++j) if(a[i][j]) return;
        flag = 1;
        return;
    }
    int b[5][7];
    for(int i = 0; i < 5; ++i) for(int j = 0; j < 7; ++j) b[i][j] = a[i][j];
    for(int i = 0; i < 5; ++i) {
        for(int j = 0; j < 7; ++j) {
            if(a[i][j] && i < 4 && a[i][j] != a[i + 1][j]) {
                swap(a[i][j], a[i + 1][j]); for(int k = 0; k < 5; ++k) down(k);
                while(clear());
                dfs(x + 1);
            }
            if(flag) {
                st[++top][0] = i; st[top][1] = j; st[top][2] = 1;
                return;
            }
            for(int I = 0; I < 5; ++I) for(int J = 0; J < 7; ++J) a[I][J] = b[I][J];
            if(a[i][j] && i > 0 && a[i][j] != a[i - 1][j] && !a[i - 1][j]) {
                swap(a[i][j], a[i - 1][j]); for(int k = 0; k < 5; ++k) down(k);
                while(clear());
                dfs(x + 1);
            }
            if(flag) {
                st[++top][0] = i; st[top][1] = j; st[top][2] = -1;
                return;
            }
            for(int I = 0; I < 5; ++I) for(int J = 0; J < 7; ++J) a[I][J] = b[I][J];
        }
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < 5; ++i) {
        int x, j = 0; while(scanf("%d", &x) && x) a[i][j++] = x;
    }
    dfs(1);
    if(!flag) puts("-1");
    else {
        for(int i = n; i; --i) printf("%d %d %d\n", st[i][0], st[i][1], st[i][2]);
    }
}