描述

Mayan puzzle是最近流行起來的一個游戲。游戲界面是一個7行5列的棋盤，上面堆放著一些方塊，方塊不能懸空堆放，即方塊必須放在最下面一行，或者放在其他方塊之上。游戲通關是指在規定的步數內消除所有的方塊，消除方塊的規則如下：

1、每步移動可以且僅可以沿橫向（即向左或向右）拖動某一方塊一格：當拖動這一方塊時，如果拖動后到達的位置（以下稱目標位置）也有方塊，那么這兩個方塊將交換位置（參見圖6到圖7）；如果目標位置上沒有方塊，那么被拖動的方塊將從原來的豎列中抽出，并從目標位置上掉落（直到不懸空，參見圖1和圖2)；

2、任一時刻，如果在一橫行或者豎列上有連續三個或者三個以上相同顏色的方塊，則它們將立即被消除（參見圖1到圖3）。

注意：
a) 如果同時有多組方塊滿足消除條件，幾組方塊會同時被消除（例如下面圖4，三個顏色為1的方塊和三個顏色為2的方塊會同時被消除，最后剩下一個顏色為2的方塊）。

b) 當出現行和列都滿足消除條件且行列共享某個方塊時，行和列上滿足消除條件的所有方塊會被同時消除（例如下面圖5所示的情形，5個方塊會同時被消除）。

3、方塊消除之后，消除位置之上的方塊將掉落，掉落后可能會引起新的方塊消除。注意：掉落的過程中將不會有方塊的消除。

上面圖1到圖3給出了在棋盤上移動一塊方塊之后棋盤的變化。棋盤的左下角方塊的坐標為（0, 0），將位于（3, 3）的方塊向左移動之后，游戲界面從圖1變成圖2所示的狀態，此時在一豎列上有連續三塊顏色為4的方塊，滿足消除條件，消除連續3塊顏色為4的方塊后，上方的顏色為3的方塊掉落，形成圖3所示的局面。

格式

輸入格式

第一行為一個正整數n，表示要求游戲關的步數。

接下來的5行，描述7*5的游戲界面。每行若干個整數，每兩個整數之間用一個空格隔開，每行以一個0 結束，自下向上表示每豎列方塊的顏色編號（顏色不多于10種，從1開始順序編號，相同數字表示相同顏色）。

輸入數據保證初始棋盤中沒有可以消除的方塊。

輸出格式

如果有解決方案，輸出n行，每行包含3個整數x，y，g，表示一次移動，每兩個整數之間用一個空格隔開，其中（x，y）表示要移動的方塊的坐標，g表示移動的方向，1表示向右移動，-1表示向左移動。注意：多組解時，按照x為第一關鍵字，y為第二關鍵字，1優先于-1，給出一組字典序最小的解。游戲界面左下角的坐標為(0, 0)。
如果沒有解決方案，輸出一行，包含一個整數-1。

樣例1

樣例輸入1[復制]

3 1 0 2 1 0 2 3 4 0 3 1 0 2 4 3 4 0

樣例輸出1[復制]

2 1 1 3 1 1 3 0 1

限制

3s

提示

?

　　超復雜爆搜，沒別的法了。。。。

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxx=10,maxy=20,maxc=20; 4 int n,c;//n表示步數，c表示方塊顏色數 5 int a[maxx][maxy];//存圖 6 int cnt[maxc];//記錄每種顏色方塊的個數 7 bool f[maxx][maxy]; 8 int ans[maxx][3]; 9 10 void fall(int x){//第 x行下落構圖 11 for(int i=0;i<7;i++){ 12 if(a[x][i]==0){ 13 int j=i+1; 14 while(j<7&&a[x][j]==0) 15 j++; 16 if(j==7) 17 return; 18 else swap(a[x][i],a[x][j]); 19 } 20 } 21 } 22 23 bool clear(){ 24 25 bool flag=false; 26 for(int i=0;i<5;i++){//橫坐標 27 for(int j=0;j<7;j++){//縱坐標 28 if(a[i][j]==0) 29 continue; 30 if(i<3&&a[i][j]==a[i+1][j]&&a[i][j]==a[i+2][j]){//橫向消 31 f[i][j]=true; 32 f[i+1][j]=true; 33 f[i+2][j]=true; 34 } 35 if(j<5&&a[i][j]==a[i][j+1]&&a[i][j]==a[i][j+2]){//縱向消 36 f[i][j]=true; 37 f[i][j+1]=true; 38 f[i][j+2]=true; 39 } 40 } 41 } 42 43 for(int i=0;i<5;i++){ 44 for(int j=0;j<7;j++){ 45 if(f[i][j]==true){//(i,j)需要被消掉 46 flag=true; 47 cnt[a[i][j]]--;//顏色減少 48 a[i][j]=0; 49 f[i][j]=false; 50 } 51 } 52 } 53 54 for(int i=0;i<5;i++) 55 fall(i);//消完之后再下落 56 57 return flag;//返回true說明還有可能繼續消 58 } 59 60 int check(){//輸出方塊顏色最少的那個顏色個數 61 int minc=0; 62 for (int i=1;i<=c;i++){ 63 if(cnt[i]!=0){ 64 if (minc==0||minc>cnt[i]){ 65 minc=cnt[i]; 66 } 67 } 68 } 69 return minc; 70 } 71 72 void print(){//輸出答案 73 74 for (int i = 1; i <= n; i++) 75 printf("%d %d %d\n", ans[i][0], ans[i][1], ans[i][2]); 76 77 exit(0);//結束程序 78 } 79 void dfs(int move){//move 移動步數 80 81 int mem[maxx][maxy]; 82 int memc[maxc]; 83 memcpy(mem,a,sizeof(a)); 84 memcpy(memc,cnt,sizeof(cnt)); 85 86 for(int i=0;i<5;i++){//橫坐標 87 for(int j=0;a[i][j]!=0&&j<7;j++){//縱坐標 88 for (int k=1;k>=-1;k-=2){//右移左移兩種情況，先算右移 89 if(i+k>=0&&i+k<5){//判斷邊界 90 if ((k==-1&&a[i-1][j]!=0)||a[i][j]==a[i+k][j])//如果左邊有方塊或者相鄰的方塊同色,不需考慮 91 continue; 92 93 ans[move][0]=i;//記錄移動信息 94 ans[move][1]=j; 95 ans[move][2]=k; 96 swap(a[i][j], a[i+k][j]);//交換 97 98 fall(i);//處理交換后的影響 99 fall(i+k); 100 101 while (clear()==true);//消去再組合 102 int tmp=check();//tmp是當前顏色最少的方塊的個數 103 if(move==n){//n步 104 if(tmp==0)//方塊完 105 print();//滿足條件，輸出 106 } 107 else if(tmp>2)//找下一步 108 dfs(move+1); 109 110 memcpy(a,mem,sizeof(mem));//相當于回溯，把操作之前的恢復原狀 111 for (int i = 1; i <= c; i++) 112 cnt[i] = memc[i]; 113 } 114 } 115 } 116 } 117 118 } 119 120 int main(){ 121 scanf("%d", &n); 122 memset(a, 0, sizeof(a)); 123 memset(cnt, 0, sizeof(cnt)); 124 memset(ans, 0, sizeof(ans)); 125 memset(f, 0, sizeof(f)); 126 c = 0; 127 int tmp; 128 for (int i = 0; i < 5; i++) 129 for (int j = 0; j <= 7; j++){ 130 scanf("%d", &tmp); 131 if (tmp == 0) 132 break; 133 a[i][j] = tmp; 134 c = max(c, tmp); 135 cnt[tmp]++;//每種方塊的數量 136 } 137 dfs(1); 138 printf("-1\n");//能走到這一步說明沒走print(),即消不完 139 return 0; 140 }

?

轉載于:https://www.cnblogs.com/CXCXCXC/p/4783328.html

總結

以上是生活随笔為你收集整理的NOIP Mayan游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。