[题解]Mayan游戏

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

提示

样例输入的游戏局面如图6到图11所示。依次移动的三步是:(2,1)处的方格向右移动,(3,1)处的方格向右移动,(3,0)处的方格向右移动,最后可以将棋盘上所有方块消除。

数据规模如下:
对于30%的数据,初始棋盘上的方块都在棋盘的最下面一行;
对于100%的数据,0 < n ≤ 5。

来源

NOIp2011提高组Day1第三题

(转自:https://vijos.org/p/1738)



  题目意思应该还是很容易懂。首先是数据范围小,限时长,所以很可能是搜索。仔细想以后发现也不太可能是状压

dp之类的,就开始来思考搜索。

  首先思考深搜还是广搜。因为一是字典序最小,而是保存的量比较大都至少是一个5 * 7的数组或是5个vector

所以深搜的速度会稍微快一些(广搜会把一层都搜完才会扩展),内存开销也会小很多

  接下来开始思考剪枝,有下面几种方案

  1)因为是字典序最小,所以当左边有方块的时候从右向左移动不如从左向右移动(减去将近一半的节点)

  2)源方块和目标方块颜色一样不需要移动,因为原来的图像看起来并没有改变

  3)一种颜色剩余的数量大于0但是不足3个,返回

  剪枝思考完毕了后,接下来是这个游戏特有的一些部分

  1)下落,这个比较简单,就不多说了,看代码

  2)消除,消除可以先标记,并不是直接消除,另外定一个5 * 7的数组,当某一位需要消除时将对应位上标为1

另外为了快捷可以3个单位地判断是否可以消除,另外在消除时还要加一个返回值判断是否消除了方块,因为消除完有

方块下落仍然会肯能产生消除,例如:

绿色消除后变成

最后红色的块也被消除



 Code

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<cctype>
  6 #include<cstdlib>
  7 #include<cmath>
  8 using namespace std;
  9 typedef bool boolean;
 10 template<typename T>
 11 inline void readInteger(T& u){
 12     char x;
 13     while(!isdigit((x = getchar())));
 14     for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘);
 15     ungetc(x, stdin);
 16 }
 17 typedef class GameObject{
 18     public:
 19         int lines[5][7];
 20         int status[5];
 21         GameObject(){
 22             memset(lines, 0, sizeof(lines));
 23             memset(status, 0, sizeof(status));
 24         }
 25         void fallingDown(){
 26             for(int i = 0; i < 5; i++){
 27                 int c = 0;
 28                 for(int j = 0; j < 7; j++){
 29                     if(lines[i][j] != 0){
 30                         lines[i][c++] = lines[i][j];
 31                         if(c - 1 != j)
 32                             lines[i][j] = 0;
 33                     }
 34                 }
 35                 status[i] = c;
 36             }
 37         }
 38         boolean clean(){
 39             GameObject b;
 40             boolean aFlag = false;
 41             for(int i = 0; i < 5; i++){
 42                 for(int j = 0; j < 5; j++){
 43                     if(lines[i][j] == lines[i][j + 1] && lines[i][j + 1] == lines[i][j + 2] &&
 44                         lines[i][j] != 0){
 45                         b[i][j] = b[i][j + 1] = b[i][j + 2] = -1;
 46                     }
 47                 }
 48             }
 49
 50             for(int i = 0; i < 7; i++){
 51                 for(int j = 0; j < 3; j++){
 52                     if(lines[j][i] == lines[j + 1][i] && lines[j + 1][i] == lines[j + 2][i] &&
 53                         lines[j][i] != 0){
 54                         b[j][i] = b[j + 1][i] = b[j + 2][i] = -1;
 55                     }
 56                 }
 57             }
 58
 59             for(int i = 0; i < 5; i++){
 60                 for(int j = 0; j < 7; j++){
 61                     if(b[i][j] < 0){
 62                         lines[i][j] = 0;
 63                         aFlag = true;
 64                     }
 65                 }
 66             }
 67             return aFlag;
 68         }
 69         boolean move(int x, int y, int direc){
 70             if(x < 0 || x >= 5)        return false;
 71             if((x + direc) < 0 || (x + direc) >= 5)    return false;
 72             if(direc == -1 && lines[x - 1][y] != 0)    return false;
 73             if(lines[x][y] == lines[x + direc][y])    return false;
 74             swap(lines[x][y], lines[x + direc][y]);
 75             fallingDown();
 76             while(clean()) fallingDown();
 77             return true;
 78         }
 79         int size(){
 80             int result = 0;
 81             for(int i = 0; i < 5; i++)
 82                 result += status[i];
 83             return result;
 84         }
 85         int* operator [](int pos){
 86             return &lines[pos][0];
 87         }
 88 }GameObject;
 89 int n;
 90 GameObject starter;
 91 const int mover[2] = {1, -1};
 92 inline void init(){
 93     readInteger(n);
 94     for(int i = 0, a; i < 5; i++){
 95         readInteger(a);
 96         while(a != 0){
 97             starter[i][starter.status[i]++] = a;
 98             readInteger(a);
 99         }
100     }
101 }
102 int x[6];
103 int y[6];
104 int d[6];
105 void search(GameObject status, int depth){
106     if(depth > n){
107         if(status.size() > 0)    return;
108         for(int i = 1; i <= n; i++){
109             printf("%d %d %d\n", x[i], y[i], d[i]);
110         }
111         exit(0);
112     }
113
114     for(int i = 0; i < 5; i++){
115         for(int j = 0; j < status.status[i]; j++){
116             for(int k = 0; k < 2; k++){
117                 GameObject before = status;
118                 if(before.move(i, j, mover[k])){
119                     x[depth] = i;
120                     y[depth] = j;
121                     d[depth] = mover[k];
122                     search(before, depth + 1);
123                 }
124             }
125         }
126     }
127 }
128 int main(){
129     freopen("mayan.in", "r", stdin);
130     freopen("mayan.out", "w", stdout);
131     init();
132     search(starter, 1);
133     printf("-1");
134     return 0;
135 }
时间: 08-29

[题解]Mayan游戏的相关文章

洛谷P1312 [NOIOP2011提高组 Day1T3]Mayan游戏

Mayan游戏 题目描述 Mayan puzzle是最近流行起来的一个游戏.游戏界面是一个 7 行5 列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上.游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下: 1 .每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时,如果拖动后到达的位置(以下称目标位置)也有方块,那么这两个方块将 交换位置(参见输入输出样例说明中的图6 到图7 ):如果目标位置上没有方块,那么被拖动的

【noip2011】【codevs1136】Mayan游戏

3.Mayan 游戏(mayan.cpp/c/pas)[问题描述]Mayan puzzle 是最近流行起来的一个游戏.游戏界面是一个7 行5 列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上.游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下:1.每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时,如果拖动后到达的位置(以下称目标位置)也有方块,那么这两个方块将交换位置(参见输入输出样例说明中的图6 到图7):如果

noip提高组2011 Mayan游戏

Mayan游戏 描述 Mayan puzzle是最近流行起来的一个游戏.游戏界面是一个7行5列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上.**游戏通关是指在规定的步数内消除所有的方块,**消除方块的规则如下: 1.每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时,如果拖动后到达的位置(以下称目标位置)也有方块,那么这两个方块将交换位置(参见图6到图7):如果目标位置上没有方块,那么被拖动的方块将从原来的竖列中抽出,并从

[noip2011 d1t3] Mayan游戏

无脑码农题== 烦的是很多细节,把几个主要过程分开写,化整为零会清楚很多 1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 #define mxcol 12 7 int map[10][10]; 8 int goal; 9 struct data{ 10 int x,y,w; 11 }ans[10];

mayan游戏

原题网上去看吧,太长了这里就不贴了╮(╯_╰)╭ 这道题简直毒瘤啊啊,,,超级长的搜索...由于bfs空间遭不住,所以选择了dfs,然后就是十分烦人的移动.下落和清除的函数,过程繁复,下面贴出代码: #include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<algorithm> using namespace std; int n,a[10][

NOIP2011 Mayan游戏(搜索)

第一反应是搜索题,想了一下如果用BFS的话,由于状态过多,可能超内存,因此我用的DFS. 这里我们讨论一下剪枝条件: 如果当前状态有一种颜色的数量小于3,那么这种颜色就无法被消除,因此我们可以提前退出迭代. 如果两个连着的方块颜色是相同的话,我们不用交换. 如果两个非空的方块交换,我们只用考虑左边那个方块右移,而不用考虑右边方块左移的情况,这样就能做到右移优先. 如果一个方块是空的,它的右边非空,我们就只用考虑它右边的方块左移,当枚举到它右边方块的时候也不需要再考虑左移的情况. 注意下落清除方块

NOIp 2011 mayan游戏 搜索

搜索. 因为要求字典序最小 所以都右移 除非那个方格为空. 代码如下: 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #define For(i,x,y) for(int i=x;i<=y;++i) 6 using namespace std; 7 int a[10][10]; 8 int cnt[10];int n; int ncnt

[NOIP2011提高组day1]-3-mayan游戏

3.Mayan 游戏 (mayan.cpp/c/pas) [问题描述] Mayan puzzle 是最近流行起来的一个游戏.游戏界面是一个 7行 5 列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上.游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下: 1.  每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时,如果拖动后到达的位置(以下称目标位置)也有方块,那么这两个方块将交换位置(参见输入输出样例说明中的图 6

codevs 1512 转向游戏 题解

Codevs 1512转向游戏 题解 时间限制: 1 s 空间限制: 1000 KB 题目等级 : 白银 Silver 题解 题目描述 Description 小明自认为方向感很好,请小红来测试.小红先让小明面对北方立正站好,然后发出"向左转""向右转"或"向后转"的命令.每个命令执行后,小明都正确地说出了他面对的方向.小红的命令共N个(1≤n≤10000),请你统计小明说[南]的次数. 命令是以数字方式表达: 0---向左转 1---向右转 2