「NOIP2011」Mayan游戏

传送门
Luogu

解题思路

爆搜，并考虑几个剪枝。

• 不交换颜色相同的方块（有争议，但是可以过联赛数据 \(Q \omega Q\)）
• 左边为空才往左换
• 右边不为空才往右换

因为对于两个相邻方块，右边往左换和左边往右换是等价的，同时还可以保证字典序最小。

细节注意事项

• 爆搜题，你们懂的。。。

参考代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
    s = f ? -s : s;
}

int n, a[10][10], la[10][10][10], ans[10][10], mark[10][10];

inline bool remv() {
    int flag = 0;
    for (rg int i = 1; i <= 5; ++i)
        for (rg int j = 1; j <= 7; ++j)
            if (a[i][j]) {
                if (i > 1 && i < 5 && a[i][j] == a[i - 1][j] && a[i][j] == a[i + 1][j])
                    flag = 1, mark[i][j] = mark[i - 1][j] = mark[i + 1][j] = 1;
                if (j > 1 && j < 7 && a[i][j] == a[i][j - 1] && a[i][j] == a[i][j + 1])
                    flag = 1, mark[i][j] = mark[i][j - 1] = mark[i][j + 1] = 1;
            }
    if (!flag) return 0;
    for (rg int i = 1; i <= 5; ++i)
        for (rg int j = 1; j <= 7; ++j)
            if (mark[i][j])
                mark[i][j] = 0, a[i][j] = 0;
    return 1;
}

inline void upt() {
    for (rg int i = 1; i <= 5; ++i) {
        int s = 0;
        for (rg int j = 1; j <= 7; ++j) {
            if (!a[i][j]) ++s;
            else if (s) a[i][j - s] = a[i][j], a[i][j] = 0;
        }
    }
}

inline void mv(int i, int j, int t) {
    swap(a[i][j], a[i + t][j]);
    do { upt(); } while (remv());
}

inline bool check() {
    for (rg int i = 1; i <= 5; ++i)
        if (a[i][1]) return 0;
    return 1;
}

inline void dfs(int x) {
    if (check()) {
        for (rg int i = 1; i < x; ++i)
            printf("%d %d %d\n", ans[0][i], ans[1][i], ans[2][i]);
        exit(0);
    }
    if (x > n) return;
    memcpy(la[x], a, sizeof a);
    for (rg int i = 1; i <= 5; ++i)
        for (rg int j = 1; j <= 7; ++j)
            if (a[i][j]) {
                if (i < 5 && a[i + 1][j] != a[i][j]) {
                    mv(i, j, 1);
                    ans[0][x] = i - 1, ans[1][x] = j - 1, ans[2][x] = 1;
                    dfs(x + 1);
                    memcpy(a, la[x], sizeof la[x]);
                    ans[0][x] = 0, ans[1][x] = 0, ans[2][x] = 0;
                }
                if (i > 1 && a[i - 1][j] == 0) {
                    mv(i, j, -1);
                    ans[0][x] = i - 1, ans[1][x] = j - 1, ans[2][x] = -1;
                    dfs(x + 1);
                    memcpy(a, la[x], sizeof la[x]);
                    ans[0][x] = 0, ans[1][x] = 0, ans[2][x] = 0;
                }
            }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
#endif
    read(n);
    for (rg int i = 1; i <= 5; ++i)
        for (rg int j = 1; j <= 8; ++j) {
            read(a[i][j]); if (a[i][j] == 0) break;
        }
    dfs(1);
    puts("-1");
    return 0;
}

完结撒花 \(qwq\)

「NOIP2011」Mayan游戏

原文：https://www.cnblogs.com/zsbzsb/p/11759300.html