题意
Mayan puzzle是一个游戏。界面是一个 7 行5 列的棋盘,上面堆放着一些方块,方块不能悬空堆放。
具体规则:
1. 每步移动可以且仅可以沿横向拖动某一方块一格:当拖动这一方块时,如果拖动后到达的位置;
如果目标位置上没有方块,那么被拖动的方块将从原来的竖列中抽出,并从目标位置上掉落;
2.任一时刻,如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块,则它们将立即被消除
注意:
a) 如果同时有多组方块满足消除条件,几组方块会同时被消除。
b) 当出现行和列都满足消除条件且行列共享某个方块时,行和列上满足消除条件的所有方块会被同时消除。
c) 方块消除之后,消除位置之上的方块将掉落,掉落后可能会引起新的方块消除。注意:掉落的过程中将不会有方块的消除。
题解
暴力dfs(注意从左下角开始,并且按照字典序(这样搜到的第一种就是字典序最小的))并不断对每个方块进行向左和向右两种操作(先向右)
剪枝:
1.交换两个颜色相同的块没有意义
2.一个块的左边是非空块时不需要考虑左移,(会和之前的块右移重复)即只有当左块为空时才左移
3.如果有一种颜色当前的块数目x满足1<=x<=2,则不肯能消完,退出
4.dfs时先考虑右移(这样搜到的第一种就是字典序最小的)
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
int n,map[9][7],x[1000],y[1000],way[1000],p=0;
bool if_can=false; //判断是否可以
void outputmap(){
cout<<"-----------------"<<endl;
for (int i=7;i>=1;i--){
for (int j=1;j<=5;j++)
cout<<map[i][j]<<' ';
cout<<endl;
}
cout<<"-----------------"<<endl;
}
int else_num(){
int sum=0;
for (int i=1;i<=7;i++)
for (int j=1;j<=5;j++)
if (map[i][j]) sum++;
return sum;
}//剩余方块个数
int del(){
bool pd=true;
int k,j,i;
int map2[8][6];
for (i=1;i<=7;i++)
for (j=1;j<=5;j++)
map2[i][j]=map[i][j];
for (i=1;i<=7;i++){
for (j=1;j<=3;j++)
if (map[i][j]!=0&&map[i][j]==map[i][j+1]&&map[i][j+1]==map[i][j+2]){
for (k=j;map[i][k]==map[i][j];k++){
map2[i][k]=0;
pd=false;
}
j=k+1;
}
}
for (j=1;j<=5;j++){
for (i=1;i<=5;i++)
if (map[i][j]!=0&&map[i][j]==map[i+1][j]&&map[i+1][j]==map[i+2][j]){
for (k=i;map[k][j]==map[i][j];k++){
map2[k][j]=0;
pd=false;
}
i=k+1;
}
}
for (i=1;i<=7;i++)
for (j=1;j<=5;j++)
map[i][j]=map2[i][j];
if (pd) return 0;
else return 1;
}
void drop1(){
for (int j=1;j<=5;j++){
for (int i=7;i>=1;i--){
if (map[i][j]==0){
for (int k=i;k<7;k++)
map[k][j]=map[k+1][j];
}
}
}
}
void drop(){
int len[6];
memset(len,0,sizeof(len));
for (int j=1;j<=5;j++){
for (int i=7;i>=1;i--)
if (map[i][j]) {
len[j]=i;
break;
}
for (int i=len[j];i>=1;i--){
if (!map[i][j]) {
for (int ij=i;ij<=7;ij++)
map[ij][j]=map[ij+1][j];
}
}
}
}
void swap(int &a,int &b){
int t;
t=a;a=b;b=t;
}
int able(){
int pd[11];
memset(pd,0,sizeof(pd));
for (int i=1;i<=7;i++)
for (int j=1;j<=5;j++)
pd[map[i][j]]++;
for (int i=1;i<=10;i++)
if (pd[i]>=1&&pd[i]<=2) return 1;
return 0;
}
void dfs(int num){
drop();
while (del()){ //消去可以消的
drop(); //悬空块掉落
}
if (able()) return;
if (num==n+1){
if (else_num()==0) {
//outputmap();
for (int i=1;i<=n;i++)
cout<<y[i]-1<<' '<<x[i]-1<<' '<<way[i]<<endl;
exit(0);
if_can=true;
}
return;
}
int map_back[8][6];
for (int i=1;i<=7;i++) for (int j=1;j<=5;j++) map_back[i][j]=map[i][j];
for (int j=1;j<=5;j++)
for (int i=1;i<=7;i++) {
if (map[i][j]){
if (map[i][j]!=map[i][j+1]&&j<5) {
x[num]=i;y[num]=j;way[num]=1;
swap(map[i][j+1],map[i][j]);
dfs(num+1);
}
for (int i=1;i<=7;i++) for (int j=1;j<=5;j++) map[i][j]=map_back[i][j];
if (map[i][j-1]==0&&j>1) {
x[num]=i;y[num]=j;way[num]=-1;
swap(map[i][j-1],map[i][j]);
dfs(num+1);
}
for (int i=1;i<=7;i++) for (int j=1;j<=5;j++) map[i][j]=map_back[i][j];
}
}
}
int main(){
memset(map,0,sizeof(map));
cin>>n;
for(int i=1;i<=5;i++){
int j=0,t;
cin>>t;
while(t!=0){
j++;
map[j][i]=t;
cin>>t;
}
}
//outputmap();
dfs(1);
if (!if_can) cout<<-1<<endl;
return 0;
}