题解 P1312 【Mayan游戏】

ZIXT · 2019-07-10 21:04:16 · 题解

平民AC，特点可能是模拟部分对码力的需求较小（存疑）
首先定义地图，方便复制以及传参

struct Filed{
    int d[10][20];
    Filed (){
        memset(d,0,sizeof(d));
    }
    int& operator () (int x,int y){ //重载运算符方便访问 
        return d[x+2][y+2]; //设置偏移量防止数组越界，减少判断 
    }
    bool isEmpty(){
        for(int i=2;i<7;i++){
            if(d[i][2]) return false; //[2]是最底层，最底层为空可判断整张图空 
        }
        return true;
    }
};  

然后模拟，因为至少需要一次下落和消去判断才能确定是否稳定， 所以stable初始为false

Filed update(Filed now, int x, int y, int g){
    bool stable=false;  //标记是否完成 
    swap(now(x+g,y),now(x,y));
    while(true){
        //下落
        for(int i=0; i<5; i++){ //从底往上，色块悬空就下落
            for(int j=1; j<7; j++){
                if(now(i,j) && !now(i,j-1)){
                    stable=false; //用于检测消去后是否无悬空
                    for(int k=j-1; k>=0; k--){
                        if(now(i,k)) break; 
                        swap(now(i,k),now(i,k+1));
                    }
                }
            }
        }
        if(stable) break; //消去后无悬空则完成

        //消去
        Filed temp=now; //不在原图上删块，防止遗漏
        for(int i=0; i<5; i++){
            for(int j=0; j<7; j++){
                if(!now(i,j)) continue;
                int cnt=1;
                int l,r,u,d;  //左右上下 

                for(r=1; now(i+r-1,j)==now(i+r,j); r++) cnt++;
                for(l=-1; now(i+l+1,j)==now(i+l,j); l--) cnt++;
                if(cnt>=3){
                    for(int k=i+l+1; k<=i+r-1; k++) temp(k,j)=0;
                }

                cnt=1;
                for(u=1; now(i,j+u-1)==now(i,j+u); u++) cnt++;
                for(d=-1; now(i,j+d+1)==now(i,j+d); d--) cnt++;
                if(cnt>=3){
                    for(int k=j+d+1; k<=j+u-1; k++) temp(i,k)=0;
                }
            }
        }
        now=temp;
        stable=true;
    }
    return now;
}

完整代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

int n;
struct Filed{
    int d[10][20];
    Filed (){
        memset(d,0,sizeof(d));
    }
    int& operator () (int x,int y){ //重载运算符方便访问 
        return d[x+2][y+2]; //设置偏移量防止数组越界，减少判断 
    }
    bool isEmpty(){
        for(int i=2;i<7;i++){
            if(d[i][2]) return false; //[2]实际是最滴层，最底层为空可判断整张图空 
        }
        return true;
    }
};  

inline void swap (int &a,int &b){
    int t=a;
    a=b;
    b=t;
}
Filed update(Filed now, int x, int y, int g){
    bool stable=false;  //标记是否完成 
    swap(now(x+g,y),now(x,y));
    while(true){
        //下落
        for(int i=0; i<5; i++){
            for(int j=1; j<7; j++){
                if(now(i,j) && !now(i,j-1)){
                    stable=false;
                    for(int k=j-1; k>=0; k--){
                        if(now(i,k)) break; 
                        swap(now(i,k),now(i,k+1));
                    }
                }
            }
        }
        if(stable) break;
        //消去
        Filed temp=now;
        for(int i=0; i<5; i++){
            for(int j=0; j<7; j++){
                if(!now(i,j)) continue;
                int cnt=1;
                int l,r,u,d;  //左右上下 

                for(r=1; now(i+r-1,j)==now(i+r,j); r++) cnt++;
                for(l=-1; now(i+l+1,j)==now(i+l,j); l--) cnt++;
                if(cnt>=3){
                    for(int k=i+l+1; k<=i+r-1; k++) temp(k,j)=0;
                }

                cnt=1;
                for(u=1; now(i,j+u-1)==now(i,j+u); u++) cnt++;
                for(d=-1; now(i,j+d+1)==now(i,j+d); d--) cnt++;
                if(cnt>=3){
                    for(int k=j+d+1; k<=j+u-1; k++) temp(i,k)=0;
                }
            }
        }
        now=temp;
        stable=true;
    }
    return now;
}

struct Opt{
    int x,y,g;
};
vector<Opt> ans;
bool dfs(int u, Filed now){
    if(u==n){
        if(now.isEmpty()) return true;
        return false;
    }
    for(int i=0; i<5; i++){
        for(int j=0; j<7; j++){
            if(now(i,j)){
                if(i<4 && now(i,j)!=now(i+1,j)){
                    ans.push_back({i,j,1});
                    if(dfs(u+1,update(now,i,j,1))) return true; 
                    ans.pop_back();
                }
                if(i>0 && !now(i-1,j)){
                    ans.push_back({i,j,-1});
                    if(dfs(u+1,update(now,i,j,-1))) return true;    
                    ans.pop_back();
                }
            }
        }
    }
    return false;
}
int main(){
    Filed s;
    scanf("%d",&n);
    for(int i=0;i<5;i++){
        for(int j=0;;j++){
            scanf("%d",&s(i,j));
            if(!s(i,j)) break;
        }
    }
    if(dfs(0,s)){
        for(int i=0;i<ans.size();i++){
            printf("%d %d %d\n",ans[i].x,ans[i].y,ans[i].g);
        }
    }else{
        printf("-1");
    }
    return 0;
}