P1312 样例都过不了求调
  • 板块题目总版
  • 楼主SunSkydp
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/7/3 22:51
  • 上次更新2023/10/27 21:57:18
查看原帖
P1312 样例都过不了求调
375241
SunSkydp楼主2022/7/3 22:51

样例都过不了求调,我明天早上起来再看,谢谢大佬。
题目在这里:P1312[NOIP2011 提高组] Mayan 游戏

#include <bits/stdc++.h> 
using namespace std;
int n;
struct dot{ //步骤记录点
    int x, y, g;
};
struct node{ //搜索结点
    int d; 
    vector<int> chess[5];
    vector<dot> v;
};
node pop(node v) { //消除操作
    node t = v; 
    vector<int> move[5]; //记录需要消除的块
    for(int i = 0; i < 5; i++) { //复制
        for(int j = 0; j < t.chess[i].size(); j++) {
            move[i].push_back(0);
        }
    }
    for(int i = 0; i < 5; i++) { //找到消除块
        for(int j = 0; j < t.chess[i].size(); j++) {
            if(j <= t.chess[i].size() - 3 && t.chess[i][j] == t.chess[i][j + 1] && t.chess[i][j + 1] == t.chess[i][j + 2]) {
                move[i][j] = move[i][j + 1] = move[i][j + 2] = 1;
            }
            if(i <= 2 && t.chess[i][j] == t.chess[i + 1][j] && t.chess[i + 1][j] == t.chess[i + 2][j]) {
                move[i][j] = move[i + 1][j] = move[i + 2][j] = 1;
            } 
        }
    }
    for(int i = 0; i < 5; i++) { //进行消除
        for(int j = 0; j < t.chess[i].size(); j++) {
            if(move[i][j] == 1) {
                t.chess[i][j] = 0;
                move[i][j] = 0;
                if(j != t.chess[i].size() - 1) {
                    for(int k = j + 1; k < t.chess[i].size(); k++) {
                        t.chess[i][k - 1] = t.chess[i][k];
                        move[i][k - 1] = move[i][k];
                    }
                }
                t.chess[i].pop_back();
                move[i].pop_back();
            }
        }
    }
    return t;
} 
void solve(node t) { //输出最终步骤
    for(int i = 0; i < t.v.size(); i++) {
        cout << t.v[i].x << " " << t.v[i].y << " " << t.v[i].g << "\n";
    }
    exit(0); //直接结束程序
}
void dfs(node v) { //搜索
    node t = v;
    if(t.d >= n) {
        bool flag = true;
        for(int i = 0; i < 5; i++) if(t.chess[i].size() != 0) flag = false;
        if(flag) solve(t); //消除完了
        else return ;
    }
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < t.chess[i].size(); j++) {
            t = v;
            if(i == 4) goto LEFT;
            /*往右移动*/
            t.v.push_back((dot){i, j, 1});
            if(t.chess[i + 1].size() - 1 < j) {
                t.chess[i + 1].push_back(t.chess[i][j]);
                if(j != t.chess[i].size() - 1) {
                    for(int k = j + 1; k < t.chess[i].size(); k++) {
                        t.chess[i][k - 1] = t.chess[i][k];
                    }
                }
                t.chess[i].pop_back();
            }
            else {
                swap(t.chess[i][j], t.chess[i + 1][j]);
            }
            t = pop(t);
            t.d++;
            dfs(t);
            if(i == 0) continue;
            /*往左移动*/
            LEFT:
            t = v;
            t.v.push_back((dot){i, j, -1});
            if(t.chess[i - 1].size() - 1 < j) {
                t.chess[i - 1].push_back(t.chess[i][j]);
                if(j != t.chess[i].size() - 1) {
                    for(int k = j + 1; k < t.chess[i].size(); k++) {
                        t.chess[i][k - 1] = t.chess[i][k];
                    }
                }
                t.chess[i].pop_back();
            }
            else {
                swap(t.chess[i][j], t.chess[i + 1][j]);
            }
            t = pop(t);
            t.d++;
            dfs(t);
        }
    }
}
int main() {
    cin >> n;
    node s;
    s.d = 0;
    for(int i = 0; i < 5; i++) { //输入
        int x;
        while(cin >> x) {
            if(x == 0) break;
            s.chess[i].push_back(x);
        }
    }
    dfs(s);
    puts("-1\n"); //无解
    return 0;
}
2022/7/3 22:51
加载中...