[NOIP2011]Mayan游戏题解

题目大意：

　　有一个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
",ansx[i],ansy[i],ansz[i]);
79     else printf("-1");
80     return 0;
81 }

[NOIP2011]Mayan游戏 题解

相关推荐

[NOIP2011]Mayan游戏题解