1755 字
9 分钟
[NOIP2011] 玛雅游戏
2017-07-27
题解
BFS

【问题描述】#

Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个7 行5 列的棋盘，上面堆放着一些方块，方块不能悬空堆放，即方块必须放在最下面一行，或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块，消除方块的规则如下：

  1. 每步移动可以且仅可以沿横向（即向左或向右）拖动某一方块一格：当拖动这一方块时，如果拖动后到达的位置（以下称目标位置）也有方块，那么这两个方块将交换位置（参见输入输出样例说明中的图6 到图7）；如果目标位置上没有方块，那么被拖动的方块将从原来的竖列中抽出，并从目标位置上掉落（直到不悬空，参见下面图1 和图2）； 5211920921a01.png

  2. 任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则它们将立即被消除（参见图1 到图3）。 53446976e072a.png 注意：

    • 如果同时有多组方块满足消除条件，几组方块会同时被消除（例如下面图4，三个颜色为1 的方块和三个颜色为2 的方块会同时被消除，最后剩下一个颜色为2 的方块）。
    • 当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除（例如下面图5 所示的情形，5 个方块会同时被消除）。

  3. 方块消除之后，消除位置之上的方块将掉落，掉落后可能会引起新的方块消除。注意：掉落的过程中将不会有方块的消除。
    上面图1 到图3 给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为（0, 0），将位于（3, 3）的方块向左移动之后，游戏界面从图1 变成图2 所示的状态，此时在一竖列上有连续三块颜色为4 的方块，满足消除条件，消除连续3 块颜色为4 的方块后，上方的颜色为3 的方块掉落，形成图3 所示的局面。

【输入】#

输入文件mayan.in，共6 行。
第一行为一个正整数n，表示要求游戏通关的步数。
接下来的5 行，描述7*5 的游戏界面。每行若干个整数，每两个整数之间用一个空格隔开，每行以一个0 结束，自下向上表示每竖列方块的颜色编号（颜色不多于10 种，从1 开始顺序编号，相同数字表示相同颜色）。
输入数据保证初始棋盘中没有可以消除的方块。

【输出】#

输出文件名为mayan.out。
如果有解决方案，输出n 行，每行包含3 个整数x，y，g，表示一次移动，每两个整数之间用一个空格隔开，其中（x，y）表示要移动的方块的坐标，g 表示移动的方向，1 表示向右移动，-1 表示向左移动。注意：多组解时，按照x 为第一关健字，y 为第二关健字，1优先于-1，给出一组字典序最小的解。游戏界面左下角的坐标为（0，0）。
如果没有解决方案，输出一行，包含一个整数-1。

mayan.in#

3
1 0
2 1 0
2 3 4 0
3 1 0
2 4 3 4 0

mayan.out#

2 1 1
3 1 1
3 0 1

【输入输出样例说明】#

按箭头方向的顺序分别为图6 到图11 19512145e77e.png 样例输入的游戏局面如上面第一个图片所示，依次移动的三步是：（2，1）处的方格向右移动，（3，1）处的方格向右移动，（3，0）处的方格向右移动，最后可以将棋盘上所有方块消除。

【数据范围】#

对于30%的数据，初始棋盘上的方块都在棋盘的最下面一行；
对于100%的数据，0 < n≤5。

题解#

大暴搜
读完题先看数据范围
发现这道题的 n 很小
感觉应该可以搜
然后想到了BFS
一个一个的试
现在的问题就是如何消除和下落在消除的时候横着扫一遍竖着扫一遍
两个for打上标记
然后一遍循环搞掉标记的点
在BFS传参数的时候要注意备份用 memcpy();
在搜的时候及时退出exit(0);
否则可能被卡

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
#include <cstdlib>
using namespace std;
//#define WILDRAGE 1
int a[6][8];
bool over[6][8];
void print(const int c[6][8])
{
    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= 7; j++)
            printf("%d ", c[i][j]);
        printf("\n");
    }
    printf("\n");
}
bool ok(const int c[6][8])
{
    //return 0;
    for (int i = 1; i <= 5; i++)
    {
        if (c[i][1])
            return 0;
    }
    return 1;
}
bool remove(int c[6][8])
{
    int it1, it2;
    for (int i = 1; i <= 5; i++)
    {
        it1 = it2 = 1;
        while (1)
        {
            while (c[i][it1] != 0 && it1 <= 7)
                it1++;
            it2 = it1;
            while (c[i][it2] == 0 && it2 <= 7)
                it2++;
            if (it2 != 8)
                swap(c[i][it2], c[i][it1]);
            else
                break;
        }
    }
    // memset(over,0,sizeof(over));
    int times = 1;
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 7; j++)
        {
            if (c[i][j] && c[i][j] == c[i][j - 1])
            {
                times++;
                if (times >= 3 && times < 4)
                {
                    over[i][j - 2] = over[i][j - 1] = over[i][j] = 1;
                }
                if (times >= 4)
                    over[i][j] = 1;
            }
            else
                times = 1;
        }
    times = 1;
    for (int j = 1; j <= 7; j++)
        for (int i = 1; i <= 5; i++)
        {
            if (c[i][j] && c[i][j] == c[i - 1][j])
            {
                times++;
                if (times >= 3 && times < 4)
                {
                    over[i - 2][j] = over[i - 1][j] = over[i][j] = 1;
                }
                if (times >= 4)
                    over[i][j] = 1;
            }
            else
                times = 1;
        }
    bool yes = 0;
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 7; j++)
            if (over[i][j])
                yes = 1, over[i][j] = 0, c[i][j] = 0;
    if (!yes)
        return 0;
    //int it1, it2;
    for (int i = 1; i <= 5; i++)
    {
        it1 = it2 = 1;
        while (1)
        {
            while (c[i][it1] != 0 && it1 <= 7)
                it1++;
            it2 = it1;
            while (c[i][it2] == 0 && it2 <= 7)
                it2++;
            if (it2 != 8)
                swap(c[i][it2], c[i][it1]);
            else
                break;
        }
    }
    return 1;
}
struct data
{
    int x, y, t;
};
stack<data> op;
stack<data> ans;
int n;
void dfs(int t, const int c[6][8])
{
    if (t == n)
    {
#ifdef WILDRAGE
        print(c);
#endif
        if (ok(c))
        {
            while (!op.empty())
            {
                ans.push(op.top());
                op.pop();
            }
            while (!ans.empty())
            {
                printf("%d %d %d\n", ans.top().x - 1, ans.top().y - 1, ans.top().t);
                ans.pop();
            }
            exit(0);
        }
        return;
    }
    else
    {
        int s[6][8];
        for (int i = 1; i <= 5; i++)
        {
            for (int j = 1; j <= 7; j++)
            {
                if (c[i][j] && i + 1 <= 5)
                {
                    op.push((data){i, j, 1});
                    memcpy(s, c, sizeof(s));
                    swap(s[i][j], s[i + 1][j]);
#ifdef WILDRAGE
//print(s);
#endif
                    while (remove(s))
                        ;
#ifdef WILDRAGE
                    printf("%d %d %d\n", i, j, 1);
                    print(s);
#endif
                    dfs(t + 1, s);
                    op.pop();
                }
                if (c[i][j] && i - 1 > 0 && !c[i - 1][j])
                {
                    op.push((data){i, j, -1});
                    memcpy(s, c, sizeof(s));
                    swap(s[i][j], s[i - 1][j]);
#ifdef WILDRAGE
//print(s);
#endif
                    while (remove(s))
                        ;
#ifdef WILDRAGE
                    printf("%d %d %d\n", i, j, -1);
                    print(s);
#endif
                    dfs(t + 1, s);
                    op.pop();
                }
            }
        }
    }
}
int main()
{
#ifndef WILDRAGE
    freopen("mayan.in", "r", stdin);
    freopen("mayan.out", "w", stdout);
#endif
    int s;
    scanf("%d", &n);
    for (int i = 1; i <= 5; i++)
    {
        int j = 0;
        while (scanf("%d", &s))
        {
            if (s == 0)
                break;
            a[i][++j] = s;
        }
        //a[i][0] = j;
    }
#ifdef WILDRAGE
    print(a);
#endif
    dfs(0, a);
    printf("-1\n");
}
[NOIP2011] 玛雅游戏
https://www.nekomio.com/posts/44/
作者
NekoMio
发布于
2017-07-27
许可协议
CC BY-NC-SA 4.0
BZOJ 2510 弱题
BZOJ 2090 [Poi2010] Monotonicity 2
京ICP备19044785号-1
© 2025 NekoMio. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari