A1103 [2011T3 Mayan游戏]

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

const int W = 5;   // 5 列
const int H = 7;   // 7 行
const int MAXC = 11;

int board[W][H];   // board[x][y]，0 表示该格没有方块
int n;             // 要求通关的步数

vector<array<int, 3>> path;          // 已经走过的操作
unordered_map<unsigned long long, int> visited;  // 棋盘 -> 已用掉的最多剩余步数

// 棋盘是否已经清空
bool emptyBoard() {
    for (int x = 0; x < W; x++) {
        for (int y = 0; y < H; y++) {
            if (board[x][y]) return false;
        }
    }
    return true;
}

// 反复消除所有可以消掉的方块，中间掉落的方块不会在掉落过程中被消除
void eliminate() {
    while (true) {
        bool del[W][H] = {};
        bool any = false;

        // 竖列上连续三个及以上相同颜色
        for (int x = 0; x < W; x++) {
            int y = 0;
            while (y < H) {
                if (!board[x][y]) {
                    y++;
                    continue;
                }
                int y2 = y + 1;
                while (y2 < H && board[x][y2] == board[x][y]) y2++;
                if (y2 - y >= 3) {
                    for (int k = y; k < y2; k++) del[x][k] = true;
                    any = true;
                }
                y = y2;
            }
        }

        // 横行上连续三个及以上相同颜色
        for (int y = 0; y < H; y++) {
            int x = 0;
            while (x < W) {
                if (!board[x][y]) {
                    x++;
                    continue;
                }
                int x2 = x + 1;
                while (x2 < W && board[x2][y] == board[x][y]) x2++;
                if (x2 - x >= 3) {
                    for (int k = x; k < x2; k++) del[k][y] = true;
                    any = true;
                }
                x = x2;
            }
        }

        if (!any) break;

        // 同时消除，然后上面的方块落下来
        for (int x = 0; x < W; x++) {
            int write = 0;
            for (int y = 0; y < H; y++) {
                if (!del[x][y]) board[x][write++] = board[x][y];
            }
            for (int y = write; y < H; y++) board[x][y] = 0;
        }
    }
}

// 把 (x, y) 处的方块沿 g（1 向右，-1 向左）拖动一格
void applyMove(int x, int y, int g) {
    int nx = x + g;
    if (board[nx][y] != 0) {
        // 目标位置有方块，两个方块交换位置
        swap(board[x][y], board[nx][y]);
    } else {
        // 目标位置没有方块：把方块从原竖列抽出，落到目标竖列的最上面
        int color = board[x][y];
        for (int k = y; k + 1 < H; k++) board[x][k] = board[x][k + 1];
        board[x][H - 1] = 0;
        int h = 0;
        while (h < H && board[nx][h]) h++;
        board[nx][h] = color;
    }
    eliminate();
}

// 剪枝：某种颜色只剩 1 个或 2 个方块时，它们永远凑不齐三个，一定无解
bool colorPossible() {
    int cnt[MAXC] = {};
    for (int x = 0; x < W; x++) {
        for (int y = 0; y < H; y++) {
            if (board[x][y]) cnt[board[x][y]]++;
        }
    }
    for (int c = 1; c < MAXC; c++) {
        if (cnt[c] == 1 || cnt[c] == 2) return false;
    }
    return true;
}

unsigned long long hashBoard() {
    unsigned long long h = 1469598103934665603ULL;
    for (int x = 0; x < W; x++) {
        for (int y = 0; y < H; y++) {
            h ^= (unsigned long long)(board[x][y] + 1);
            h *= 1099511628211ULL;
        }
    }
    return h;
}

// 按 (x, y, g) 的字典序枚举操作，深度优先搜索，第一条找到的解就是字典序最小的解
bool dfs(int step) {
    if (emptyBoard()) return true;
    if (step >= n) return false;
    if (!colorPossible()) return false;

    unsigned long long key = hashBoard();
    auto it = visited.find(key);
    if (it != visited.end() && it->second >= n - step) return false;
    visited[key] = n - step;

    for (int x = 0; x < W; x++) {
        for (int y = 0; y < H; y++) {
            if (!board[x][y]) continue;
            for (int dir = 0; dir < 2; dir++) {
                int g = (dir == 0) ? 1 : -1;
                int nx = x + g;
                if (nx < 0 || nx >= W) continue;
                int snapshot[W][H];
                memcpy(snapshot, board, sizeof board);
                applyMove(x, y, g);
                path.push_back({x, y, g});
                if (dfs(step + 1)) return true;
                path.pop_back();
                memcpy(board, snapshot, sizeof board);
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    // 5 行，每行描述一竖列的方块颜色，自下向上，最后一个 0 表示结束
    for (int x = 0; x < W; x++) {
        int v, y = 0;
        while (cin >> v && v != 0) board[x][y++] = v;
    }

    if (dfs(0)) {
        for (const auto &mv : path) cout << mv[0] << " " << mv[1] << " " << mv[2] << "\n";
    } else {
        cout << -1 << "\n";
    }
    return 0;
}