洛谷P1312 Mayan游戏
? 解题记录 ? ? 洛谷 ? ? 搜索 ?    2018-11-13 10:10:52    516    0    0

题目描述

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

 

输入输出样例

输入样例#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

说明

【输入输出样例说明】

按箭头方向的顺序分别为图6到图11

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

【数据范围】

对于30%的数据,初始棋盘上的方块都在棋盘的最下面一行;

对于100%的数据,0<n5 。

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;
}

 

上一篇: 2018年末计划:展望未来

下一篇: 洛谷P2403 [SDOI2010]所驼门王的宝藏

516 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航