题解 P1312 【Mayan游戏】

· · 题解

无聊写了写老题目，希望能给大家一些帮助，关键点就以下几个：

  1. 向右的时候如果右方颜色相同则跳过

  2. 向左的时候如果左方并非是空，则跳过（否则可以选择其左侧方块右移，这样字典序更小）

  3. 需要更短时间的话可以根据每一步当前图的状态是否出现某种颜色小于2个来进行剪枝。因为你刷新图的时候其实就可以顺手统计，所以其实并不怎么费时，但是剪枝效果满满（当然我觉得不剪也可以就没写这个）

至于实现细节的话，掉落可以看fall的代码，刷新的时候先掉落一下，再给要消除的东西打标记。最后根据标记删除方块，步骤爆搜即可。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define REP(i,l,r) for(int i=l;i<r;++i)

const int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};

int ansx[6], ansy[6], ansmv[6];
int mp[7][5][7], N;
bool vis[5][7];

inline void hei(int d, int x, int y, int mv){
    ansx[d]=x, ansy[d]=y, ansmv[d]=mv;
}
inline bool inbound(int x, int y){ return 0<=x&&x<5&&0<=y&&y<7;}
void fall(int d){
    REP(i,0,5){ int sz=0;
        REP(j,0,7) if (mp[d][i][j])
            mp[d][i][sz++]=mp[d][i][j];
        while (sz < 7) mp[d][i][sz++] = 0;
    }
}
inline void refresh(int d){
    int tim = 0;
    for (bool cg = true; cg;){
        cg = false, fall(d);
        REP(i,0,5) REP(j,0,7) if (mp[d][i][j]){
            if (i < 3){
                if (mp[d][i][j]==mp[d][i+1][j]&&mp[d][i][j]==mp[d][i+2][j]){
                    cg = vis[i][j] = vis[i+1][j] = vis[i+2][j] = true;
                }
            }
            if (j < 5){
                if (mp[d][i][j]==mp[d][i][j+1]&&mp[d][i][j]==mp[d][i][j+2]){
                    cg = vis[i][j] = vis[i][j+1] = vis[i][j+2] = true;
                }
            }
        }
        REP(i,0,5) REP(j,0,7) if (vis[i][j]) mp[d][i][j] = vis[i][j] = 0;
    }
}
bool solve(int dep){
    REP(i,0,5) REP(j,0,7) mp[dep][i][j] = mp[dep-1][i][j];
    refresh(dep);
    if (dep == N+1){
        REP(i,0,5) if (mp[dep][i][0]) return false;
        return true;
    }
    REP(i,0,5) REP(j,0,7) if (mp[dep][i][j]){
        if (i < 4 && mp[dep][i][j]!=mp[dep][i+1][j]){    // 1
            hei(dep, i, j, 1);
            swap(mp[dep][i][j], mp[dep][i+1][j]);
            if (solve(dep+1)) return true;
            swap(mp[dep][i][j], mp[dep][i+1][j]);
        }
        if (i && !mp[dep][i-1][j]){        // -1
            hei(dep, i, j, -1);
            swap(mp[dep][i][j], mp[dep][i-1][j]);
            if (solve(dep+1)) return true;
            swap(mp[dep][i][j], mp[dep][i-1][j]);
        }
    }
    return false;
}

int main(){
    scanf("%d", &N);
    REP(i,0,5) REP(j,0,9){
        int x; scanf("%d", &x);
        if (!x) break;
        mp[0][i][j] = x;
    }
    bool fg = solve(1);
    if (fg){ REP(i,1,N+1) printf("%d %d %d\n", ansx[i],ansy[i],ansmv[i]);}
    else    puts("-1");
    return 0;
}