题意

这是一个​​十二面体拼图问题​​： ​​十二面体​​有$12$个五边形面，每个面需要放一块拼图片。 ​​拼图片​​也是五边形，每条边标有数字$0$、$1$或$2$。

​​规则​​： 相邻的两个面（共享一条边）必须满足：它们的公共边数字相同。 拼图片可以旋转（但不能翻转），有$5$种可能的摆放角度。

​​输入​​：$12$块拼图片的边标记（每块$5$个数字）。

​​输出：​​给出每块拼图片应该放在哪个面，以及如何旋转（用相邻面编号表示旋转角度）。如果无解，输出$-1$

解题思路

这道题目要求我们解决一个十二面体拼图问题，需要将$12$块五边形拼图片正确放置在十二面体的$12$个面上，使得相邻拼图片的公共边数字完全相同。

1. 问题建模

十二面体结构：十二面体有$12$个五边形面，每个面与其他$5$个面相邻。题目给出了每个面的相邻关系（$Adjacent$数组）。 拼图片：每块拼图片有$5$条边，每条边标记为$0$、$1$或$2$。拼图片可以旋转$5$个不同角度（$0°$、$72°$、$144°$、$216°$、$288°$）放置。

2. 核心算法：回溯法（$DFS$）

状态表示： $vis[i]$：标记拼图片$i$是否已被使用。 $mp[i][j]$：记录十二面体面$i$和面$j$之间共享边的数字（初始为$-1$）。 $ans[i][0]$和$ans[i][1]$：记录面$i$上放置的拼图片编号和参考边指向的相邻面。 递归过程：

1. 选择拼图片：对于当前面$cur$，遍历所有未使用的拼图片$i$。
2. 尝试旋转角度：对于拼图片$i$，尝试$5$种旋转角度（对应$j=0,1,2,3,4$）。
3. 检查合法性：检查拼图片$i$在当前旋转角度下，其边标记是否与相邻面的已有标记匹配。
4. 递归下一层：如果合法，标记拼图片$i$为已使用，更新$mp$和$ans$，递归处理下一个面$cur+1$。
5. 回溯：如果递归失败，恢复$vis$、$mp$和$ans$的状态，尝试其他拼图片或旋转角度。

3. 关键优化

剪枝：在递归过程中，如果发现当前拼图片的边标记与相邻面的已有标记冲突，立即终止当前分支的搜索。 状态复制：每次递归调用时，复制当前的$mp$状态（$mp1$），避免直接修改全局状态，简化回溯过程。

4. 输出结果

如果找到解，输出每个面放置的拼图片编号和参考边指向的相邻面。 如果无解，输出$-1$。

标程

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

bool vis[13];
int tile[13][6], ans[13][2];
int Adjacent[15][6] = { {0, 0, 0, 0, 0, 0},
                        {0, 2, 3, 4, 5, 6},
                        {0, 1, 6, 7, 11, 3},
                        {0, 1, 2, 11, 10, 4},
                        {0, 1, 3, 10, 9, 5},
                        {0, 1, 4, 9, 8, 6},
                        {0, 1, 5, 8, 7, 2},
                        {0, 8, 12, 11, 2, 6},
                        {0, 9, 12, 7, 6, 5},
                        {0, 10, 12, 8, 5, 4},
                        {0, 11, 12, 9, 4, 3},
                        {0, 7, 12, 10, 3, 2},
                        {0, 7, 8, 9, 10, 11} };

int mod(int v)
{
    return (v + 5) % 5;
}

bool dfs(int cur, int mp[][13])
{
    if(cur > 12) return true;
    int mp1[13][13];
    for(int i = 1; i <= 12; i++){
        if(!vis[i]){
            for(int j = 0, k; j < 5; j++){ // 枚举面=tile的5个位置
                memcpy(mp1, mp, sizeof(mp1));
                for(k = 0; k < 5; k++){
                    if(mp1[cur][Adjacent[cur][k + 1]] == -1){ // 判断是否合法
                        mp1[cur][Adjacent[cur][k + 1]] = mp1[Adjacent[cur][k + 1]][cur] = tile[i][mod(j + k)];
                    }else if(mp1[cur][Adjacent[cur][k + 1]] != tile[i][mod(j + k)])
                        break;
                }
                if(k >= 5){
                    vis[i] = true;
                    ans[cur][0] = i; ans[cur][1] = Adjacent[cur][mod(5 - j) + 1]; // 记录当前放的tile和参考边所对应的面
                    if(dfs(cur + 1, mp1)) return true;
                    vis[i] = false;
                }
            }
        }
    }
    return false;
}

int main()
{
    int mp[13][13];
    for(int i = 1; i <= 12; i++)
        for(int j = 0; j < 5; j++)
            scanf("%d", &tile[i][j]);
    memset(mp, -1, sizeof(mp));
    memset(vis, 0, sizeof(vis));
    if(dfs(1, mp)){
        for(int i = 1; i <= 12; i++){
            printf("%d %d\n", ans[i][0], ans[i][1]);
        }
    }else printf("-1\n");
    return 0;
}