洛谷P1312 Mayan游戏

题目

搜索+剪枝

对于每个操作都只需要模拟就可轻松得出每一步操作的代码。

这个题需要考虑回溯操作，由于搜索是在一棵搜索树中，因此我们可以记录每一个深度的回溯状态，仅仅用一个数组会出现状态转移失误的情况，所以需要用多个数组。然后考虑剪枝，如果交换不交换没有区别，则不需要交换，而且i向左交换等同于i-1向右交换，判断一下是否有有漏解就可以无重复的枚举了。

#include <bits/stdc++.h>
#include <vector>
using namespace std;
struct dat
{
    int x, y, g;
} ans[10001];
int n, now, flag;
int b[7][9], a[7][9];
int v[7][9][10];// v是每一列从下到上的数排列起来，需要多加一位从而方便回溯，dp和搜索在无法再找到解题方式的时候，增加一维状态往往是一种好方法。
void cv (int now)//now是当前处于第几步 *之后*
{
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 7; j++)
            v[i][j][now] = a[i][j];
}

void print()
{
    for (int i = 1; i <= 5; i++, puts(""))
        for (int j = 1; j <= 7; j++)
            printf("%d ", a[i][j]);
} 
void down()//使当前所有浮在空中的方块下落。
{
    for (int i = 1; i <= 5; i++)
    {
        int cnt = 0;
        for (int j = 1; j <= 7; j++)
            if (a[i][j])
            {
                a[i][++cnt] = a[i][j];
                if (cnt != j)
                    a[i][j] = 0;
            }
    }
}
bool lose()
{
    int flag = 0;
    memset(b, 0, sizeof(b));
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 7; j++)
        {
            if (!a[i][j])continue; 
            if (i + 1 <= 5 && i - 1 >= 1 && a[i][j] == a[i + 1][j] && a[i][j] == a[i - 1][j])//三个可以同时消除。
                b[i][j] = b[i + 1][j] = b[i - 1][j] = 1, flag = 1;
            if (j + 1 <= 7 && j - 1 >= 1 && a[i][j] == a[i][j + 1] && a[i][j] == a[i][j - 1])
                b[i][j] = b[i][j - 1] = b[i][j + 1] = 1, flag = 1;
        }
    if (!flag) return 0;
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 7; j++)
        {
            if (b[i][j])
                a[i][j] = 0;
        }
//  print();
    return 1;
}
void move(int i, int j, int g)
{
    swap(a[i][j], a[i + g][j]);
    down();
    while (lose())//如果出现空缺，则使他们下移。 
        down();
}
bool check()//判断当前是否所有数都被删除了。
{
    for (int i = 1; i <= 5; i++)
        if (a[i][1])//如果存在还不为0的数，说明不行。
            return 0;
    return 1;
}
void dfs(int now)
{
    if (check() && now == n + 1)//如果答案正确，就直接输出答案。
    {
        flag = 1;
        for (int i = 1; i <= n; i++)
            printf("%d %d %d\n", ans[i].x, ans[i].y, ans[i].g);
        exit(0);
    }
    if (now == n + 1) return;
    cv(now);//将当前的状态记录下来。
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 7; j++)
        {
            if (!a[i][j]) continue;
            if (i + 1 <= 5 && a[i + 1][j] != a[i][j])//既然相等，就不需要互换了
            {
                ans[now].g = 1; ans[now].x = i - 1, ans[now].y = j - 1;//原题中的坐标是以0,0开始的，所以都减一。
                move(i, j, 1);
                dfs(now + 1);
                for (int k = 1; k <= 5; k++)
                    for (int l = 1; l <= 7; l++)
                        a[k][l] = v[k][l][now];
                ans[now].g = 0, ans[now].x = 0, ans[now].y = 0;
            }
            if (i - 1 >= 1 && a[i - 1][j] == 0)
            {
                ans[now].g = -1, ans[now].x = i - 1, ans[now].y = j - 1;
                move(i, j, -1);
                dfs(now + 1);
                for (int k = 1; k <= 5; k++)
                    for (int l = 1; l <= 7; l++)
                        a[k][l] = v[k][l][now];
                ans[now].g = 0, ans[now].x = 0, ans[now].y = 0; 
            }
        }
}
int main()
{
    scanf("%d", &n);//游戏通关步数
    for (int i = 1; i <= 5; i++)
        for (int j = 1, ha; j <= 8; j++)
        {
            scanf("%d", &ha);
            if (ha == 0) break;
            a[i][j] = ha;
        }   
    dfs(1);
    printf("-1");
    return 0;
}
/*
3
1 0 
2 1 0 
2 1 4 0 
2 4 0 
4 0
*/

洛谷P1312 Mayan游戏

原文：https://www.cnblogs.com/liuwenyao/p/11787935.html