Luogu

分析

显然可以直接爆搜,我们只要按字典序顺序搜就好了。

然后是一些剪枝:

  • 不交换两个颜色相同的方块。(这个根据对题意的理解有争议?)
  • 向左移时如果左边不是空的就不移。(因为你显然可以让左边那个右移,字典序更小。)
  • 如果任何时候某种有的颜色 $\leq 2$,显然无解。

然后就是码码码了。其实也不是很码

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n,a[10][10][10],vis[10][10],o[15];
int ansx[10],ansy[10],ansd[10];

inline void fall(int d) {
    for (re int i=1;i<=5;++i) { int c=0;
        for (re int j=1;j<=7;++j)
            if (a[d][i][j]) a[d][i][++c]=a[d][i][j];
        for (re int j=c+1;j<=7;++j) a[d][i][j]=0;
    }
}

inline void clear(int d) {
    while ("longge ak ioi") {
        memset(vis,0,sizeof(vis)); int flag=0;
        for (re int i=1;i<=5;++i)
            for (re int j=1;j<=7;++j) {
                if (!a[d][i][j]) continue;
                if (i<=3)
                    if (a[d][i][j]==a[d][i+1][j]&&a[d][i][j]==a[d][i+2][j])
                        flag=vis[i][j]=vis[i+1][j]=vis[i+2][j]=1;
                if (j<=5)
                    if (a[d][i][j]==a[d][i][j+1]&&a[d][i][j]==a[d][i][j+2])
                        flag=vis[i][j]=vis[i][j+1]=vis[i][j+2]=1;
            }
        if (!flag) break;
        for (re int i=1;i<=5;++i)
            for (re int j=1;j<=7;++j)
                if (vis[i][j]) a[d][i][j]=0;
        fall(d);
    }
}

inline int dfs(int dep) {
    for (re int i=1;i<=5;++i)
        for (re int j=1;j<=7;++j)
            a[dep][i][j]=a[dep-1][i][j];
    fall(dep),clear(dep);
    for (re int i=1;i<=10;++i) o[i]=0;
    for (re int i=1;i<=5;++i)
        for (re int j=1;j<=7;++j)
            ++o[a[dep][i][j]];
    for (re int i=1;i<=10;++i) if (o[i]&&o[i]<=2) return 0;
    if (dep==n+1) {
        for (re int i=1;i<=5;++i)
            if (a[dep][i][1]) return 0;
        return 1;
    }
    for (re int i=1;i<=5;++i)
        for (re int j=1;j<=7;++j) {
            if (!a[dep][i][j]) continue;
            if (i<5&&a[dep][i+1][j]!=a[dep][i][j]) {
                ansx[dep]=i,ansy[dep]=j,ansd[dep]=1;
                swap(a[dep][i+1][j],a[dep][i][j]);
                if (dfs(dep+1)) return 1;
                swap(a[dep][i+1][j],a[dep][i][j]);
            }
            if (i>1&&!a[dep][i-1][j]) {
                ansx[dep]=i,ansy[dep]=j,ansd[dep]=-1;
                swap(a[dep][i-1][j],a[dep][i][j]);
                if (dfs(dep+1)) return 1;
                swap(a[dep][i-1][j],a[dep][i][j]);
            }
        }
    return 0;
}

int main() {
    n=read();
    for (re int i=1;i<=5;++i)
        for (re int j=1;j<=8;++j) {
            a[0][i][j]=read();
            if (!a[0][i][j]) break;
        }
    if (dfs(1)) {
        for (re int i=1;i<=n;++i)
            printf("%d %d %d\n",ansx[i]-1,ansy[i]-1,ansd[i]);
    }
    else puts("-1");
    return 0;
}
最后修改:2019 年 10 月 28 日 08 : 21 PM