UNAC 100 被Hack求条

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

int n;
unordered_map<string,int> visited;

void drop(int board[7][5]) {
    for (int x = 0; x < 5; x++) {
        vector<int> tmp;
        for (int y = 0; y < 7; y++)
            if (board[y][x] != 0) tmp.push_back(board[y][x]);
        for (int y = 0; y < 7; y++)
            board[y][x] = (y < (int)tmp.size() ? tmp[y] : 0);
    }
}

bool eliminate(int board[7][5]) {
    bool marked[7][5] = {0};
    bool has = 0;
    for (int y = 0; y < 7; y++) {
        int cur = board[y][0], cnt = 1;
        for (int x = 1; x < 5; x++) {
            if (board[y][x] == cur && cur != 0) cnt++;
            else {
                if (cnt >= 3) for (int i = x - cnt; i < x; i++) marked[y][i] = 1;
                cur = board[y][x]; cnt = 1;
            }
        }
        if (cnt >= 3) for (int i = 5 - cnt; i < 5; i++) marked[y][i] = 1;
    }
    for (int x = 0; x < 5; x++) {
        int cur = board[0][x], cnt = 1;
        for (int y = 1; y < 7; y++) {
            if (board[y][x] == cur && cur != 0) cnt++;
            else {
                if (cnt >= 3) for (int i = y - cnt; i < y; i++) marked[i][x] = 1;
                cur = board[y][x]; cnt = 1;
            }
        }
        if (cnt >= 3) for (int i = 7 - cnt; i < 7; i++) marked[i][x] = 1;
    }

    // 清除
    for (int y = 0; y < 7; y++)
        for (int x = 0; x < 5; x++)
            if (marked[y][x]) { board[y][x] = 0; has = 1; }

    if (has) drop(board);
    return has;
}

void Eliminate(int board[7][5]) {
    while (eliminate(board));
}

bool move(int currBoard[7][5], int x, int y, int g, int newBoard[7][5]) {
    int x2 = x + g;
    if (x2 < 0 || x2 >= 5 || currBoard[y][x] == 0) return 0;
    memcpy(newBoard, currBoard, sizeof(int)*7*5);

    if (newBoard[y][x2] != 0) {               // 交换
        swap(newBoard[y][x], newBoard[y][x2]);
    } else {                                    // 抽出+掉落
        int color = newBoard[y][x];
        newBoard[y][x] = 0;
        // 原列掉落
        vector<int> tmp;
        for (int yy = 0; yy < 7; yy++) if (newBoard[yy][x] != 0) tmp.push_back(newBoard[yy][x]);
        for (int yy = 0; yy < 7; yy++) newBoard[yy][x] = (yy < (int)tmp.size() ? tmp[yy] : 0);
        // 目标列掉落
        tmp.clear();
        for (int yy = 0; yy < 7; yy++) if (newBoard[yy][x2] != 0) tmp.push_back(newBoard[yy][x2]);
        tmp.push_back(color);
        for (int yy = 0; yy < 7; yy++) newBoard[yy][x2] = (yy < (int)tmp.size() ? tmp[yy] : 0);
    }
    return 1;
}

// 棋盘哈希
string Hash(int board[7][5]) {
    string s;
    for (int y = 0; y < 7; y++)
        for (int x = 0; x < 5; x++)
            s += to_string(board[y][x]) + ",";
    return s;
}

// 判空
bool isClear(int board[7][5]) {
    for (int y = 0; y < 7; y++)
        for (int x = 0; x < 5; x++)
            if (board[y][x] != 0) return 0;
    return 1;
}

// DFS：step为已走步数，path记录移动序列
bool dfs(int step, int currBoard[7][5], vector<tuple<int,int,int>>& path) {
    if (step == n) {
        if (isClear(currBoard)) {
            for (auto &[x,y,g] : path) cout << x << " " << y << " " << g << "\n";
            return 1;
        }
        return 0;
    }

    for (int x = 0; x < 5; x++) {
        for (int y = 0; y < 7; y++) {
            for (int g : {1, -1}) {
                int nxt[7][5];
                if (!move(currBoard, x, y, g, nxt)) continue;
                Eliminate(nxt);
                string h = Hash(nxt);
                if (visited.count(h) && visited[h] <= step + 1) continue;
                visited[h] = step + 1;
                path.emplace_back(x, y, g);
                if (dfs(step + 1, nxt, path)) return 1;
                path.pop_back();
            }
        }
    }
    return 0;
}

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

    cin >> n;
    int init[7][5] = {0};
    for (int x = 0; x < 5; x++) {
        vector<int> col;
        int c;
        while (cin >> c && c != 0) col.push_back(c);
        for (int i = 0; i < (int)col.size() && i < 7; i++) init[i][x] = col[i];
    }

    if (isClear(init)) { cout << "-1\n"; return 0; }
    visited[Hash(init)] = 0;
    vector<tuple<int,int,int>> path;
    if (!dfs(0, init, path)) cout << "-1\n";
    return 0;
}