【NOIP 2011 提高组 Day1】mayan 游戏
程序员文章站
2022-04-02 18:58:09
...
题目
题解:
–要我说,这道题极其恶趣味,就是dfs加疯狂模拟,大概1个多小时就能打完,但是如果有小错误,可以找2个多小时呢,代码大概150~200行,加油!
–下面稍微有一点的优化:
1. 按照题目最优方案顺序找,找到的第一组解,就是最优解(先x从小到大,再是y从小到大,每个先右移)
2. 对于两个相同颜色的图块,交换没有意义
3. 两个左右相邻且不为空的图块,把左边的右移,一定比把右边的左移更优
剩下的就是坚贞不屈的精神了,加油!
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=10;
int n;
bool flag;
int g[MAXN][MAXN];
struct hehe{
int x;
int y;
int p;
}ans[MAXN];
bool ok(int g[MAXN][MAXN]){
for(int i=0;i<7;i++)
for(int j=0;j<5;j++)
if(g[i][j])
return 0;
return 1;
}
void fall(int g[MAXN][MAXN]){
for(int j=0;j<5;j++)
for(int i=0;i<7;i++)
if(g[i][j]){
int x=i;
while(x>0&&!g[x-1][j]){
swap(g[x][j],g[x-1][j]);
x--;
}
}
}
bool xiao(int g[MAXN][MAXN]){
int can=0;
int G[MAXN][MAXN]={0};
for(int i=0;i<7;i++){
for(int j=0;j<5;j++){
if(g[i][j]){
if(j<3&&g[i][j]==g[i][j+1]&&g[i][j]==g[i][j+2]){
G[i][j]=1;
G[i][j+1]=1;
G[i][j+2]=1;
}
if(i<5&&g[i][j]==g[i+1][j]&&g[i][j]==g[i+2][j]){
G[i][j]=1;
G[i+1][j]=1;
G[i+2][j]=1;
}
}
}
}
for(int i=0;i<7;i++){
for(int j=0;j<5;j++){
if(G[i][j]){
g[i][j]=0;
can=1;
}
}
}
return can;
}
void dfs(int t,int g[MAXN][MAXN]){
if(t>n){
if(ok(g)){
flag=1;
for(int i=1;i<=n;i++)
cout<<ans[i].x<<" "<<ans[i].y<<" "<<ans[i].p<<endl;
}
return ;
}
int sum[MAXN];
memset(sum,0,sizeof(sum));
for(int i=0;i<7;i++)
for(int j=0;j<5;j++)
sum[g[i][j]]++;
for(int i=1;i<10;i++)
if(sum[i]==1||sum[i]==2)
return ;
int G[MAXN][MAXN];
for(int j=0;j<4;j++){
for(int i=0;i<7;i++){
if(g[i][j]!=g[i][j+1]){
for(int x=0;x<7;x++)
for(int y=0;y<5;y++)
G[x][y]=g[x][y];
if(g[i][j]){
ans[t].x=j;
ans[t].y=i;
ans[t].p=1;
}
else{
ans[t].x=j+1;
ans[t].y=i;
ans[t].p=-1;
}
swap(G[i][j],G[i][j+1]);
fall(G);
while(xiao(G))
fall(G);
dfs(t+1,G);
if(flag)
return ;
}
}
}
}
int main(){
// freopen("mayan.in","r",stdin);
// freopen("mayan.out","w",stdout);
cin>>n;
for(int j=0;j<5;j++){
for(int i=0;;i++){
scanf("%d",&g[i][j]);
if(!g[i][j])
break;
}
}
dfs(1,g);
if(!flag)
cout<<-1;
return 0;
}
上一篇: 小 P 的牧场
下一篇: 笑喷,精妙绝伦的逗B