1. 题目

传送门= ̄ω ̄=

2. 题解

哇,超级大爆搜。。。

剪枝如下:

  • 相同颜色的格子互换位置没有任何意义~
  • (左移格子X)与(右移X左边的那个格子)是等价的,且(右移X左边的那个格子)更优先
  • 若某一种颜色的格子数目在$[1,2]$中,则说明这个状态不可能有解。

上面三个剪枝即可通过此题,然而我只想得到第一个。。。

QvQ

话说我倒是发现一个可以简化代码的方法:用vector存状态,这样删除一个格子后它上面的格子因为vector而会自动掉下来不需要写代码特殊处理(类似于链表)

代码:

#include <bits/stdc++.h>

using namespace std;

int n;

bool bkr[5][7], bkc[5][7];

struct state
{
    vector<int> d[5]; int col[11];
    bool empty()
    {
        for (int i = 0; i < 5; i += 1)
            if (!d[i].empty()) return 0;
        return 1;
    }
    int clear()
    {
        memset(bkr, 0, sizeof(bkr)), memset(bkc, 0, sizeof(bkc));
        for (int i = 0; i < 5; i += 1)
            for (int j = 0; j < d[i].size(); j += 1)
                if (!bkr[i][j])
                {
                    int k = 1;
                    for (; k + i < 5; k += 1)
                    {
                        if (j >= d[k + i].size()) break;
                        if (d[k + i][j] != d[i][j]) break;
                    }
                    if (k >= 3) for (int l = 0; l < k; l += 1) bkr[l + i][j] = 1;
                }
        for (int i = 0; i < 5; i += 1)
            for (int j = 0; j < d[i].size(); j += 1)
                if (!bkc[i][j])
                {
                    int k = 1;
                    for (; k + j < d[i].size(); k += 1)
                        if (d[i][k + j] != d[i][j]) break;
                    if (k >= 3) for (int l = 0; l < k; l += 1) bkc[i][l + j] = 1;
                }
        int res = 0;
        for (int i = 0; i < 5; i += 1)
            for (int j = d[i].size() - 1; j >= 0; j -= 1)
                if (bkr[i][j] || bkc[i][j])
                    res++, col[d[i][j]]--, d[i].erase(d[i].begin() + j);
        return res;
    }
    void move(int a, int b, int g)
    {
        if (g > 0)
        {
            if (d[a + 1].size() <= b)
            {
                d[a + 1].push_back(d[a][b]);
                d[a].erase(d[a].begin() + b);
            }
            else swap(d[a][b], d[a + 1][b]);
        }
        else
        {
            if (d[a - 1].size() <= b)
            {
                d[a - 1].push_back(d[a][b]);
                d[a].erase(d[a].begin() + b);
            }
            else swap(d[a][b], d[a - 1][b]);
        }
        while (clear());
    }
} bgn, nxt;

int ans[10][3];

void Dfs(state s, int cnt)
{
    if (cnt == n)
    {
        if (s.empty())
        {
            for (int i = 0; i < n; i += 1)
                printf("%d %d %d\n", ans[i][0], ans[i][1], ans[i][2]);
            exit(0);
        }
        return;
    }
    for (int i = 1; i <= 10; i += 1)
        if (s.col[i] > 0 && s.col[i] <= 2) return;
    for (int i = 0; i < 5; i += 1)
        for (int j = 0; j < s.d[i].size(); j += 1)
        {
            if (i < 4)
            {
                if (s.d[i + 1].size() > j && s.d[i + 1][j] == s.d[i][j]) continue;
                nxt = s, nxt.move(i, j, 1);
                ans[cnt][0] = i, ans[cnt][1] = j, ans[cnt][2] = 1;
                Dfs(nxt, cnt + 1);
            }
            if (i > 0 && s.d[i - 1].size() <= j)
            {
                nxt = s, nxt.move(i, j, -1);
                ans[cnt][0] = i, ans[cnt][1] = j, ans[cnt][2] = -1;
                Dfs(nxt, cnt + 1);
            }
        }
}
int main(int argc, char const* argv[])
{
    scanf("%d", &n);
    for (int i = 0, j; i < 5; i += 1)
        while (scanf("%d", &j), j)
            bgn.d[i].push_back(j), bgn.col[j]++;
    Dfs(bgn, 0), puts("-1");
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *