rockdu
题目描述
Mayan puzzle是最近流行起来的一个游戏。游戏界面是一个7 行 5×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 所示的局面。
输入输出格式
输入格式：
共 6 行。
第一行为一个正整数n，表示要求游戏通关的步数。
接下来的5行，描述7×5 的游戏界面。每行若干个整数，每两个整数之间用一个空格隔开，每行以一个0 结束，自下向上表示每竖列方块的颜色编号（颜色不多于10种，从1开始顺序编号，相同数字表示相同颜色）。
输入数据保证初始棋盘中没有可以消除的方块。
输出格式：
如果有解决方案，输出n行，每行包含 3 个整数x,y,g，表示一次移动，每两个整数之间用一个空格隔开，其中(x,y)表示要移动的方块的坐标，g 表示移动的方向，1 表示向右移动，−1表示向左移动。注意：多组解时，按照x为第一关健字，y为第二关健字，1优先于−1 ，给出一组字典序最小的解。游戏界面左下角的坐标为(0,0)。
如果没有解决方案，输出一行，包含一个整数−1。
输入输出样例
说明
【输入输出样例说明】
按箭头方向的顺序分别为图6到图11
样例输入的游戏局面如上面第一个图片所示，依次移动的三步是：(2 ,1 )处的方格向右移动，(3,1)处的方格向右移动，(3,0)处的方格向右移动，最后可以将棋盘上所有方块消除。
【数据范围】
对于30%的数据，初始棋盘上的方块都在棋盘的最下面一行；
对于100%的数据，0<n≤5 。
noip2011提高组day1第3题
NOIP前写一个爆搜，居然调出来了，泪目
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdlib>
#include<tr1/unordered_map>
using namespace std;
using namespace tr1;
const int Base = 42;
const int mod = 19260817;
unordered_map<int, int > vis;
int n, tmp[5][7];
//x y (1 < -1)
struct OPR {int x, y, d;} to;
struct Game {
int mp[5][7], id, step;
void cntid() {
id = 0;
for(register int i = 0; i < 5; ++i)
for(register int j = 0; j < 7; ++j)
id = (id * Base % mod + mp[i][j]) % mod;
id = (id * Base % mod + step) % mod;
}
void read() {
int c = -1; step = 0;
for(register int i = 0; i < 5; ++i) {
c = -1;
for(register int j = 0; c; ++j)
scanf("%d", &c), mp[i][j] = c;
}
cntid();
}
void prt() {
for(register int i = 0; i < 5; ++i) {
for(register int j = 0; mp[i][j] && j < 7; ++j)
printf("%d ", mp[i][j]);
putchar('\n');
}
putchar('\n');
}
void G() {
int mx = 0;
for(register int i = 0; i < 5; ++i) {
for(register int j = 0; j < 7;) {
if(mp[i][j]) {++j; continue;}
mx = 0;
for(register int k = j; k < 6; ++k)
mx = max(mx, (mp[i][k] = mp[i][k + 1]));
mp[i][6] = 0;
if(!mx) break;
}
}
}
void D() {
memset(tmp, 0, sizeof(tmp));
for(register int i = 0; i < 3; ++i)
for(register int j = 0; j < 7; ++j) {
if(!mp[i][j]) continue;
if(mp[i][j] == mp[i + 1][j] &&
mp[i + 1][j] == mp[i + 2][j])
tmp[i][j] = tmp[i + 1][j] = tmp[i + 2][j] = 1;
}
for(register int i = 0; i < 5; ++i)
for(register int j = 0; j < 5; ++j) {
if(!mp[i][j]) continue;
if(mp[i][j] == mp[i][j + 1] &&
mp[i][j + 1] == mp[i][j + 2])
tmp[i][j] = tmp[i][j + 1] = tmp[i][j + 2] = 1;
}
for(register int i = 0; i < 5; ++i)
for(register int j = 0; j < 7; ++j)
if(tmp[i][j]) mp[i][j] = 0;
}
void Sim() {
int lid = -1;
while(id != lid) {
lid = id, D();
G();
cntid();
}
}
int move(int x, int y, OPR & o) {
if(mp[x][y] == mp[x + 1][y])
return 0;
if(!mp[x][y]) o = (OPR) {x + 1, y, -1};
else o = (OPR) {x, y, 1};
swap(mp[x][y], mp[x + 1][y]);
return 1;
}
} st;
vector<OPR> stk;
void dfs(int step, Game u) {
if(vis[u.id]) return ;
vis[u.id] = 1;
if(step == n) {
if(u.id != step) return ;
for(register int i = 0; i < stk.size(); ++i) {
printf("%d %d %d\n", stk[i].x, stk[i].y, stk[i].d);
}
exit(0);
}
OPR now; Game nw = u;
for(register int i = 0; i < 4; ++i)
for(register int j = 0; j < 7; ++j) {
nw = u;
nw.step = step + 1;
if(!nw.move(i, j, now)) continue;
nw.Sim();
stk.push_back(now);
dfs(step + 1, nw);
stk.pop_back();
}
}
int main() {
//freopen("r.txt", "w", stdout);
scanf("%d", &n);
st.read();
dfs(0, st);
printf("-1");
return 0;
}
没有帐号? 立即注册