样例都过不了求调,我明天早上起来再看,谢谢大佬。
题目在这里: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;
}