P1312 [NOIP 2011 提高组] Mayan 游戏
YIZHIYANG初来乍到 2026-5-31 12:00:21
/*
题意：在 5*7 棋盘上进行 n 次横向移动，每次移动后模拟下落与连锁消除，求字典序最小通关方案。
思路：n<=5，直接 DFS。每步按 x、y、方向 1/-1 枚举；移动后反复执行下落和同时消除，并用颜色数量小于 3 的剪枝。
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n;
int a[5][7], an[6][3];
int mk[5][7];
void fal() {
for(int i=0;i<5;i++) {
int k=0;
for(int j=0;j<7;j++)
if(a[i][j]) a[i][k++]=a[i][j];
while(k<7) a[i][k++]=0;
}
}
bool del() {
memset(mk,0,sizeof(mk));
bool ok=0;
for(int i=0;i<5;i++) {
for(int j=0;j<7;j++) {
if(!a[i][j]) continue;
int c=a[i][j], k=i;
while(k<5&&a[k][j]==c) k++;
if(k-i>=3) {
ok=1;
for(int t=i;t<k;t++) mk[t][j]=1;
}
k=j;
while(k<7&&a[i][k]==c) k++;
if(k-j>=3) {
ok=1;
for(int t=j;t<k;t++) mk[i][t]=1;
}
}
}
if(!ok) return 0;
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(mk[i][j]) a[i][j]=0;
fal();
return 1;
}
void sim() {
fal();
while(del());
}
bool emp() {
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(a[i][j]) return 0;
return 1;
}
bool chk() {
int ct[15]={0};
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(a[i][j]) ct[a[i][j]]++;
for(int i=1;i<=10;i++)
if(ct[i]&&ct[i]<3) return 0;
return 1;
}
void mov(int x,int y,int g) {
int nx=x+g;
if(a[nx][y]) swap(a[x][y],a[nx][y]);
else {
a[nx][y]=a[x][y];
a[x][y]=0;
}
sim();
}
bool dfs(int d) {
if(d==n) return emp();
if(!chk()) return 0;
int b[5][7];
memcpy(b,a,sizeof(a));
for(int x=0;x<5;x++) {
for(int y=0;y<7;y++) {
if(!a[x][y]) continue;
for(int z=0;z<2;z++) {
int g=(z==0?1:-1);
int nx=x+g;
if(nx<0||nx>=5) continue;
if(g==-1&&a[nx][y]) continue;
an[d][0]=x;
an[d][1]=y;
an[d][2]=g;
mov(x,y,g);
if(dfs(d+1)) return 1;
memcpy(a,b,sizeof(a));
}
}
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<5;i++) {
int x,j=0;
while(cin>>x&&x) a[i][j++]=x;
}
if(dfs(0)) {
for(int i=0;i<n;i++)
cout<<an[i][0]<<" "<<an[i][1]<<" "<<an[i][2]<<"\n";
} else cout<<-1<<"\n";
return 0;
}
112 浏览1 点赞0 收藏0 评论