题目描述
玛雅难题是最近流行起来的一个游戏。
游戏界面是一个 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 所示的局面。
样例
输入样例:
3
1 0
2 1 0
2 3 4 0
3 1 0
2 4 3 4 0
输出样例:
2 1 1
3 1 1
3 0 1
样例解释
按箭头方向的顺序分别为图6到图11
样例输入的游戏局面如图6所示,依次移动的三步是:
1、(2,1)处的方格向右移动。
2、(3,1)处的方格向右移动。
3、(3,0)处的方格向右移动。
最后可以将棋盘上所有方块消除。
算法1
(暴力枚举) $O(n^2)$
因为题目要求是将输入的方格消除干净, 消除干净。
剪枝1: 如果当前剩下的方格还剩下1个,2个,那么必定不能消除干净。直接返回
剪枝2: 方格往左移动的时候,需要判断左边是否为空,如下示意:
1 2,
2方格想要与1交换,那么字典序肯定不如1方格往右移动来的小。
因此往左移动只有一种可能,右边悬空状态。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
int g[5][7], bg[5][5][7];
int cnt[11], bcnt[5][11];
bool st[5][7];
struct Path{
int x, y, d;
}path[5];
void move(int a, int b, int c){
swap(g[a][b], g[c][b]);
while (true){//一直循环,直到flag = true表示没找到可以继续消除的方格。
bool flag = true;
//处理悬空方格
for (int x = 0; x < 5; x ++ ){
int z = 0;
for (int y = 0; y < 7; y ++ )
if (g[x][y])//如果有数字就从z开始填,并且z++, 如果没数字则跳过。
g[x][z ++] = g[x][y];
while (z < 7) g[x][z ++] = 0;
}
memset(st, 0, sizeof st);
for (int x = 0; x < 5; x ++ )
for (int y = 0; y < 7; y ++ )
if (g[x][y]){
int l = x, r = x;
while (l - 1 >= 0 && g[l - 1][y] == g[x][y]) l --;
while (r + 1 < 5 && g[r + 1][y] == g[x][y]) r ++;
if (r - l + 1 >= 3){
st[x][y] = true;
flag = false;
}
else {
l = r = y;
while (l - 1 >= 0 && g[x][l - 1] == g[x][y]) l --;
while (r + 1 < 7 && g[x][r + 1] == g[x][y]) r ++;
if (r - l + 1 >= 3){
st[x][y] = true;
flag = false;
}
}
}
if (flag) break;
for (int x = 0; x < 5; x ++ )
for (int y = 0; y < 7; y ++ )
if (st[x][y]){
cnt[0] --;
cnt[g[x][y]] --;
g[x][y] = 0;
}
}
}
bool dfs(int u){
if (u == n) return !cnt[0];
for (int i = 1; i <= 10; i ++ )
if (cnt[i] == 1 || cnt[i] == 2)
return false;
memcpy(bg[u], g, sizeof g); //备份现场
memcpy(bcnt[u], cnt, sizeof cnt);
for (int x = 0; x < 5; x ++ )
for (int y = 0; y < 7; y ++ )
if (g[x][y]){
int nx = x + 1;
if (nx < 5){
path[u] = {x, y, 1};
move(x, y, nx);
if (dfs(u + 1)) return true;
memcpy(g, bg[u], sizeof g);//因为move函数后会改变原来的图形g
memcpy(cnt, bcnt[u], sizeof cnt);//move后会改变原来图形数字的数量cnt
}
nx = x - 1;
if (nx >= 0 && !g[nx][y]){//这里如果能够左移的话,必须保证左边为空,具体见剪枝2.
path[u] = {x, y, -1};
move(x, y, nx);
if (dfs(u + 1)) return true;
memcpy(g, bg[u], sizeof g);
memcpy(cnt, bcnt[u], sizeof cnt);
}
}
return false;
}
int main(){
scanf("%d", &n);
for (int x = 0; x < 5; x ++ ){
int t, y = 0;
while (scanf("%d", &t), t){
cnt[0] ++;//记录总共有多少个数
cnt[t] ++;//记录数字t的有多少个,方便dfs里剪枝
g[x][y ++] = t;
}
}
if (dfs(0)){
for (int i = 0; i < n; i ++ ) printf("%d %d %d\n", path[i].x, path[i].y, path[i].d);
}else puts("-1");
return 0;
}