题解：搜索+模拟
剪枝：
最优性剪枝：x从小到大，y从小到大，第一次搜到的就是字典序最小
的最优解。
最优性剪枝：把一个格子和左边格子交换，和左边格子和右边格
子交换是等价的，显然让左边格子和右边交换更优。
可行性剪枝：如果当前格子某个颜色个数为1或者2return 一定消不去。
最优性剪枝:相同颜色格子交换并没有什么卵用，当左边是空时和左边交换
几个操作
(1)down()函数 目的是为了让腾空的格子落下
(2)xiao()函数 目的是让三个相同颜色的格子消去
(3)check()函数 当前颜色是否都被消去了
错因：不是蠢是弱呀...，down函数写错了，还有tmp[][]不能设成
全局变量，否则回溯不了....md...orz
代码：
#include#include #include #include #define maxn 20using namespace std;int n;int map[maxn][maxn],re[maxn][maxn],ans[maxn][maxn],cnt[maxn];void read(){ scanf("%d",&n); for(int i=1;i<=5;i++){ int nu=0,x; while(1){ scanf("%d",&x); if(!x)break; map[i][++nu]=x; } }}bool check(){ for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) if(map[i][j])return false; return true;}void down(){ for(int i=1;i<=5;i++){ int nu=0,t; for(int j=1;j<=7;j++){ // if(map[i][j])map[i][++nu]=map[i][j],map[i][j]=0; //留住上面沙茶的一行，最后map[][]竟然清0了、 if(map[i][j]){t=map[i][j];map[i][j]=0;map[i][++nu]=t;} } }}bool xiao(){ bool flag=false; memset(re,0,sizeof(re)); for(int i=1;i<=5;i++){ for(int j=1;j<=7;j++){ if(map[i][j]&&map[i][j]==map[i][j-1]&&map[i][j]==map[i][j+1]) flag=true,re[i][j]=re[i][j-1]=re[i][j+1]=true; if(map[i][j]&&map[i][j]==map[i+1][j]&&map[i][j]==map[i-1][j]) flag=true,re[i][j]=re[i+1][j]=re[i-1][j]=true; } } for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) if(re[i][j])map[i][j]=0; return flag;}void dfs(int x){ if(x==n+1){ if(check()){ for(int i=1;i<=n;i++) printf("%d %d %d\n",ans[i][1]-1,ans[i][2]-1,ans[i][3]); exit(0); } return; } int tmp[20][20];memset(cnt,0,sizeof(cnt)); for(int i=1;i<=5;i++)for(int j=1;j<=7;j++)tmp[i][j]=map[i][j],cnt[map[i][j]]++; for(int i=1;i<=10;i++)if(cnt[i]==1||cnt[i]==2)return; for(int i=1;i<=5;i++){ for(int j=1;j<=7;j++){ if(map[i][j]==0)break; if(map[i][j]!=map[i+1][j]&&i!=5){ swap(map[i][j],map[i+1][j]); ans[x][1]=i,ans[x][2]=j,ans[x][3]=1; down();while(xiao())down(); dfs(x+1); for(int i=1;i<=5;i++)for(int j=1;j<=7;j++)map[i][j]=tmp[i][j]; } if(map[i-1][j]==0&&i!=1){ swap(map[i][j],map[i-1][j]); ans[x][1]=i,ans[x][2]=j,ans[x][3]=-1; down();while(xiao())down(); dfs(x+1); for(int i=1;i<=5;i++)for(int j=1;j<=7;j++)map[i][j]=tmp[i][j]; } } }}int main(){ read();dfs(1); puts("-1"); return 0;}
20180825
22:02:01
一年后凭借对题解的记忆又写了一遍....比去年好多了...
注意记录答案，如果用flag=1表示找到了答案return，
记录的答案有可能改变。
吸了氧终于过了
// luogu-judger-enable-o2#include#include #include #include using namespace std;int n;int flag;int a[10][10],ct[15];struct A{ int x,y,d;}ans[7];bool ok(){ for(int i=0;i<7;i++) { for(int j=0;j<5;j++) { if(a[i][j]) return false; } } return true;}void drop(){ for(int i=0;i<5;i++) { for(int j=0;j<7;j++) { int x=j,y=i; if(a[j][i]&&(x-1>=0&&!a[x-1][y])) { while(x-1>=0&&!a[x-1][y]) x--; a[x][y]=a[j][i]; a[j][i]=0; } } }}bool clear(){ int yes=0; int k[7][5]; memset(k,0,sizeof(k)); for(int i=0;i<7;i++) { for(int j=0;j<5;j++) { if(!a[i][j]) continue; if(j+1<5&&j-1>=0&&a[i][j]==a[i][j+1]&&a[i][j]==a[i][j-1]) yes=1,k[i][j]=k[i][j+1]=k[i][j-1]=1; if(i+1<7&&i-1>=0&&a[i][j]==a[i+1][j]&&a[i][j]==a[i-1][j]) yes=1,k[i][j]=k[i-1][j]=k[i+1][j]=1; } } for(int i=0;i<7;i++) { for(int j=0;j<5;j++) { if(k[i][j]) a[i][j]=0; } } return yes;}void dfs(int now){ int b[7][5]; if(now==n+1&&ok()) { for(int i=1;i<=n;i++) printf("%d %d %d\n",ans[i].x,ans[i].y,ans[i].d); exit(0); } if(now>=n+1) return; memset(ct,0,sizeof(ct)); for(int i=0;i<7;i++) for(int j=0;j<5;j++) b[i][j]=a[i][j],ct[b[i][j]]++; for(int i=1;i<=10;i++) if(ct[i]&&ct[i]<3) return ; for(int i=0;i<5;i++) { for(int j=0;j<7;j++) { if(!a[j][i]) continue; if(a[j][i]!=a[j][i+1]&&i+1<5) { swap(a[j][i],a[j][i+1]); drop(); while(clear()) drop(); ans[now].x=i;ans[now].y=j;ans[now].d=1; dfs(now+1); for(int c=0;c<7;c++) for(int d=0;d<5;d++) a[c][d]=b[c][d]; } if(i-1>=0&&a[j][i]!=a[j][i-1]) { swap(a[j][i],a[j][i-1]); drop();while(clear()) drop(); ans[now].x=i;ans[now].y=j;ans[now].d=-1; dfs(now+1); for(int c=0;c<7;c++) for(int d=0;d<5;d++) a[c][d]=b[c][d]; } } }}int main(){ scanf("%d",&n); for(int i=0;i<5;i++) { int cnt=0,x; while(1) { scanf("%d",&x); if(!x) break; a[cnt++][i]=x; } } dfs(1); printf("-1\n"); return 0;}