智慧珠游戏问题

解题思路

本题要求我们找到一种方案使得能用这 $12$ 个零件恰好铺满整个三角形。

本题的本质其实是一个填图问题，那么就可以考虑用 $Dancing~Links$ 来做，首先就要设法将原问题转化为一个精确覆盖问题。

首先考虑行，也就是选法，这里选法就是每种零件的每种摆法，摆法涉及到旋转、翻转、平移三种操作。一个零件通过旋转会有四种形态，翻转之后再旋转又有四种形态，一共八种形态，一共 $55$ 个格子，因此最多可以平移 $55$ 次，一共有 $12$ 个零件，因此总行数会有 $12 \times 8 \times 55 = 5280$ 行。

然后考虑列，也就是限制，第一种限制就是每个格子恰好只能放一个零件。所以用第 $1 \sim 55$ 列每列只能有一个 $1$ 来对应每个格子只能放一个零件。第二种限制是每个零件只能用一个，所以用第 $56 \sim 67$ 列每列只能有一个 $1$ 来对应每个零件只能用一个。因此总列数会有 $67$ 列。

到此我们就考虑好了十字链表的行和列，并且很直观的可以知道原问题的任意一种方案和精确覆盖问题的任意一种选法都是一一对应的。

因此我们只需要按照以上思路建图，然后跑一边精确覆盖的 $Dancing~Links$ 即可

注意，本题思路不难，难点在于建图，因为每个零件都要进行翻转和旋转操作，实现起来非常麻烦，这里有一个较为方便的操作方法，就是将所有零件都用一个正方形的字符串矩阵表示出来，然后我们对一个正方形的字符串矩阵去进行翻转和旋转操作就不会影响形状，而且相对比较方便。对应翻转，直接枚举每一行左右交换即可，而对于旋转，这里用到一个技巧，如果想要将一个正方形矩阵逆时针旋转 $90^。$，只需要先将矩阵左、右翻转，再沿着 左上$-$右下 的对角线翻转即可，而平移则只需要枚举偏移量就行了。总而言之本题的建图非常恶心。

C++ 代码

#include <iostream>
#include <cstring>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 32000;

int m = 67;
char block[12][4][5] = {
    {
        "**",
        "* "
    },
    {
        "****",
        "    ",
        "    ",
        "    "
    },
    {
        "***",
        "*  ",
        "   "
    },
    {
        "**",
        "**"
    },
    {
        "*  ",
        "*  ",
        "***"
    },
    {
        "****",
        " *  ",
        "    ",
        "    "
    },
    {
        "***",
        "* *",
        "   "
    },
    {
        "***",
        "** ",
        "   "
    },
    {
        "*** ",
        "  **",
        "    ",
        "    "
    },
    {
        " * ",
        "***",
        " * "
    },
    {
        "*  ",
        "** ",
        " **"
    },
    {
        "****",
        "*   ",
        "    ",
        "    "
    }
}; //用正方形字符矩阵表示所有零件
int l[N], r[N], u[N], d[N], s[N], row[N], col[N], idx;
int res[N], top; //存储最终选择的所有行的编号
int id[10][10]; //id[x][y] 表示 (x, y) 所在格子的编号
vector<vector<vector<int>>> sol; //存储十字链表中每一行对应的零件状态，每个状态中存储它所有点的坐标
char chr[N]; //chr[i] 表示 sol[i] 中对应零件的类型
set<vector<vector<int>>> S; //存储零件通过翻转、旋转得到的所有形状
char g[20][20]; //存储原图

void init() //初始化十字链表
{
    for(int i = 0; i <= m; i++)
    {
        l[i] = i - 1, r[i] = i + 1;
        u[i] = d[i] = i;
    }
    l[0] = m, r[m] = 0;
    idx = m + 1;
}

void rev1(char str[4][5]) //左、右翻转
{
    int len = strlen(str[0]);
    for(int i = 0, j = len - 1; i < j; i++, j--)
        for(int k = 0; k < len; k++)
            swap(str[i][k], str[j][k]);
}

void rev2(char str[4][5]) //左上-右下 斜对角线翻转
{
    int len = strlen(str[0]);
    for(int i = 0; i < len; i++)
        for(int j = 0; j < i; j++)
            swap(str[i][j], str[j][i]);
}

//str[4][5] 表示字符串矩阵
//(a, b) 表示字符串矩阵左上角的位置（偏移量）
vector<vector<int>> get(char str[4][5], int a, int b) //找出当前零件占了的所有位置的坐标
{
    vector<vector<int>> res;
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            if(str[i][j] == '*')
                res.push_back({i + a, j + b});
    return res;
}

//str[4][5] 表示字符串矩阵
//(a, b) 表示字符串矩阵左上角的位置（偏移量）
//c 表示当前字符串矩阵的类型
bool check(char str[4][5], int c, int a, int b) //判断当前零件的状态是否合法
{
    auto A = get(str, a, b);
    vector<vector<int>> B; //记录原图中所有类型为 c 的位置
    for(int i = 0; i < 10; i++)
        for(int j = 0; j <= i; j++)
            if(g[i][j] == c + 'A')
                B.push_back({i, j});
    if(B.size()) //如果原图中已经有类型为 c 的零件，则判断一下当前零件和原图中的零件能否对应上，对应上才合法
    {
        sort(A.begin(), A.end()), sort(B.begin(), B.end()); //将两个零件对应的坐标排序
        return A == B; //如果一样说明当前零件和原图中的零件一一对应，状态合法
    }

    //否则说明原图中不存在类型为 c 的零件，那么判断一定当前零件所在的位置是否合法
    for(int i = 0; i < A.size(); i++)
    {
        int x = A[i][0], y = A[i][1];
        if(x < 0 || x >= 10 || y < 0 || y >= 10) return false; //如果所在位置越界，则不合法
        if(g[x][y] != '.') return false; //如果所在位置和已有零件冲突，或所在位置在三角形以外，则不合法
    }
    return true; //否则合法
}

void add(int &hh, int &tt, int x, int y) //将 (x, y) 加入 hh 和 tt 之间
{
    row[idx] = x, col[idx] = y, s[y]++;
    u[idx] = y, d[idx] = d[y], u[d[y]] = idx, d[y] = idx;
    r[hh] = idx, l[tt] = idx, l[idx] = hh, r[idx] = tt;
    tt = idx++;
}

void remove(int p) //删除第 p 列
{
    l[r[p]] = l[p], r[l[p]] = r[p];
    for(int i = d[p]; i != p; i = d[i])
        for(int j = r[i]; j != i; j = r[j])
        {
            s[col[j]]--;
            u[d[j]] = u[j], d[u[j]] = d[j];
        }
}

void resume(int p) //恢复第 p 列
{
    for(int i = u[p]; i != p; i = u[i])
        for(int j = l[i]; j != i; j = l[j])
        {
            u[d[j]] = j, d[u[j]] = j;
            s[col[j]]++;
        }
    r[l[p]] = p, l[r[p]] = p;
}

bool dfs() //爆搜
{
        if(!r[0]) return true;

    int p = r[0];
    for(int i = r[0]; i; i = r[i])
        if(s[i] < s[p])
            p = i;

    remove(p);
    for(int i = d[p]; i != p; i = d[i])
    {
        res[++top] = row[i];
        for(int j = r[i]; j != i; j = r[j]) remove(col[j]);
        if(dfs()) return true;
        for(int j = l[i]; j != i; j = l[j]) resume(col[j]);
        top--;
    }
    resume(p);
    return false;
}

int main()
{
    //给每个格子一个唯一编号
    for(int i = 0, k = 1; i < 10; i++)
        for(int j = 0; j <= i; j++, k++)
            id[i][j] = k;

    for(int i = 0; i < 10; i++) scanf("%s", g[i]);

    init(); //初始化十字链表

    for(int i = 0; i < 12; i++)
        for(int u = 0; u < 2; u++) //翻转
        {
            for(int j = 0; j < 4; j++) //旋转
            {
                for(int a = -10; a < 10; a++) //平移（平移包含负偏移量保证枚举到所有情况）
                    for(int b = -10; b < 10; b++)
                        if(check(block[i], i, a, b)) //如果当前零件的状态合法，则将当前零件的状态存储起来
                        {
                            auto t = get(block[i], a, b); //找出当前零件占了的所有位置的坐标
                            if(S.count(t)) continue; //如果当前零件的状态已经存在，直接跳过
                            //否则说明当前零件的状态是新的，需要将它加入十字链表
                            int hh = idx, tt = idx;
                            for(int v = 0; v < t.size(); v++)
                            {
                                int x = t[v][0], y = t[v][1];
                                add(hh, tt, sol.size(), id[x][y]); //限制 1：每个格子只能放一个零件
                            }
                            add(hh, tt, sol.size(), 55 + i + 1); //限制 2：每个零件只能有 1 次
                            chr[sol.size()] = 'A' + i; //记录当前行对应的零件的类型
                            sol.push_back(t); //将当前行对应的零件状态存储起来
                            S.insert(t); //将当前状态加入
                        }
                //逆时针 90 度旋转
                rev1(block[i]);
                rev2(block[i]);
            }
            rev1(block[i]); //左、右翻转
        }

    if(dfs()) //如果有解
    {
        //将选择的方案填入图中
        for(int i = 1; i <= top; i++)
        {
            auto &points = sol[res[i]];
            char z = chr[res[i]];
            for(int j = 0; j < points.size(); j++)
            {
                int x = points[j][0], y = points[j][1];
                g[x][y] = z;
            }
        }

        //输出方案
        for(int i = 0; i < 10; i++) puts(g[i]);
    }
    else puts("No solution"); //否则无解

    return 0;
}