[NOIP2011]Mayan游戏 题解

mac2022-06-30  128

题目大意:

  有一个5*7的方格,上面有几种颜色的方块,如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块,则它们将立即被消除,方块消除之后,消除位置之上的方块将掉落。每步移动可以且仅可以沿横向拖动某一方块一格:当拖动这一方块时,如果拖动后到达的目标位置也有方块,那么这两个方块将交换位置;如果目标位置上没有方块,那么被拖动的方块将从原来的竖列中抽出,并从目标位置上掉落,直到不悬空。输入一个正整数n ,表示要求游戏通关的步数,输出方案(多组解时,按照 x 为第一关健字,y 为第二关健字,1优先于-1 ,给出一组字典序最小的解)

思路:

  因为n小于等于5,因此按字典序搜索方案,移动后按要求模拟(全零的要注意),减枝为若要移动的方块左侧不为空则该方案不是最优,可以舍去。

代码:(太丑陋了)

1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 #define copy(x,y) memcpy(x,y,sizeof(x)) 5 #define sousuo x[k]=i,y[k]=j,dfs(k+1),tot=t,copy(map,a),copy(hight,b) 6 int map[7][9],hight[7],x[6],y[6],z[6],ansx[6],ansy[6],ansz[6],i,n,tot,k; 7 bool flag; 8 9 void wk(int x,int y,int z) 10 { 11 int i,c[7][9]; 12 if (map[z][y]) i=map[x][y],map[x][y]=map[z][y],map[z][y]=i; 13 else 14 { 15 map[z][hight[z]++]=map[x][y]; 16 for (;y<hight[x];y++) map[x][y]=map[x][y+1]; 17 map[x][hight[x]--]=0; 18 } 19 for (bool f=1;f;) 20 { 21 f=0; 22 memset(c,0,sizeof(c)); 23 for (i=0;i<5;i++) 24 for (x=y=0;y<=hight[i];) 25 if (map[i][x]==map[i][y]) y++; 26 else 27 { 28 if (y-x>2) for (f=1;x<y;x++) c[i][x]=1; 29 x=y; 30 } 31 for (i=0;i<7;i++) 32 for (x=y=0;y<8;) 33 if (map[x][i]==map[y][i]) y++; 34 else 35 { 36 if (y-x>2 && map[x][i]) for (f=1;x<y;x++) c[x][i]=1; 37 x=y; 38 } 39 for (i=0;i<5;i++) 40 { 41 for (x=y=0;y<hight[i];) 42 { 43 while (c[i][y]) y++,tot--; 44 if (y==hight[i]) break; 45 map[i][x++]=map[i][y++]; 46 } 47 for (y=x;y<9;y++) map[i][y]=0; 48 hight[i]=x; 49 } 50 } 51 } 52 53 void dfs(int k) 54 { 55 if (flag) return; 56 if (k>n) 57 { 58 if (!tot) flag=1,copy(ansx,x),copy(ansy,y),copy(ansz,z); 59 return; 60 } 61 if (!tot) return; 62 int a[7][9],b[7],t=tot; 63 copy(a,map),copy(b,hight); 64 for (int i=0;i<5;i++) 65 for (int j=0;j<b[i];j++) 66 { 67 if (i<4) wk(i,j,i+1),z[k]=1,sousuo; 68 if (i && !a[i-1][j]) wk(i,j,i-1),z[k]=-1,sousuo;//jianzhi 69 } 70 } 71 72 int main() 73 { 74 scanf("%d",&n); 75 for (i=0;i<5;i++) 76 for (scanf("%d",&k);k;scanf("%d",&k)) map[i][hight[i]++]=k; 77 for (i=0;i<5;i++) tot+=hight[i]; dfs(1); 78 if (flag) for (i=1;i<=n;i++) printf("%d %d %d\n",ansx[i],ansy[i],ansz[i]); 79 else printf("-1"); 80 return 0; 81 }

 

转载于:https://www.cnblogs.com/HHshy/p/6008854.html

相关资源:JAVA上百实例源码以及开源项目
最新回复(0)