欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【NOIP 2011 提高组 Day1】mayan 游戏

程序员文章站 2022-04-02 18:58:09
...

题目

【NOIP 2011 提高组 Day1】mayan 游戏【NOIP 2011 提高组 Day1】mayan 游戏【NOIP 2011 提高组 Day1】mayan 游戏


题解:

–要我说,这道题极其恶趣味,就是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;
}
相关标签: 刷题之路