解迷建模

Oct 23, 2020 2 min read 杂谈

这次来聊点简单的，也许你偶尔有机会在地摊上看到有人摆了一堆解锁玩具，这回我们通过建模来解决当中属于迷宫类型的玩具。

魔金·円

第一图是初始状态，第二图是解开后各自的形状。为了更能理解接下来我说的，最好当然是你手上有一个一样的。

但是，事实上可以存在两种不同的初始状态，其路线也略不相同，以下会做说明。

编码

稍微操作几下，我们就会发现，它的操作很简单，它的边缘有一上一下，在中间的孔也有一左一右，即边缘的宽度小于等于中间的孔时，就可穿过一格。我们把它如下图摆放(俯视图)：

这两个disks都有一个特点，有一个孔特别长，这两个孔交错时为初始位置。我们把这个特殊的孔编号为0，然后这个孔中间一左一右大小不同，我们按小的为主方向，于是上图左边的disk从0号孔开始顺时针编码1到6，右边的disk从0号孔开始也是顺时针编码1到6。由于都是顺时针，我称它为同向的初始状态（还有一种是反向的）。

再来看，左边的disk从0孔到1孔顺时针方向的边是粗的（如下图红色圈），但右边的disk从0孔到1孔顺时针方向的边是细的（如下图蓝色圈），这也决定这两个disk是不同的，在这规定顺时针方向下粗的是disk a，细的是disk b，且a总是放左边，b放右边，如图的交错方式

观察完毕后，为了方便写成代码，我们开始对disk a进行状态描述，如下图，对孔1为例子，取它的顺时针方向的边与它作为一组，按图上次序编码，窄的为0，宽的取1

最后按定义好的方向，进行编码，得到如下的编码表：

int disk_shape[2][7][4] = {
    {
        {1, 0, 1, 0},
        {0, 1, 0, 1},
        {1, 0, 1, 0},
        {0, 1, 0, 0},
        {1, 0, 0, 1},
        {1, 0, 1, 0},
        {0, 1, 0, 1},
    },
    {
        {1, 0, 0, 1},
        {0, 1, 1, 0},
        {1, 0, 0, 1},
        {0, 1, 0, 0},
        {0, 0, 1, 0},
        {1, 0, 0, 1},
        {0, 1, 1, 0},
    },
};

有了编码，接下来的事情就是判断哪些位置能做操作了。对于每一个位置，我们都有对disk a顺时针和逆时针，对disk b顺时针和逆时针共4种操作，那直接写成代码并打印，看看哪些可以即可。

具体代码

#include <algorithm>
#include <cstdio>

int st_map[7][7][4];

void genmap()
{
    int disk_shape[2][7][4] = {
        {
            {1, 0, 1, 0},
            {0, 1, 0, 1},
            {1, 0, 1, 0},
            {0, 1, 0, 0},
            {1, 0, 0, 1},
            {1, 0, 1, 0},
            {0, 1, 0, 1},
        },
        {
            {1, 0, 0, 1},
            {0, 1, 1, 0},
            {1, 0, 0, 1},
            {0, 1, 0, 0},
            {0, 0, 1, 0},
            {1, 0, 0, 1},
            {0, 1, 1, 0},
        },
    };
    for (int dl = 0; dl < 7; ++dl)
    {
        for (int dr = 0; dr < 7; ++dr)
        {
            char s[5] = "    ";
            // 反向
            /*
            if (disk_shape[0][(dl + 0) % 7][2] <= disk_shape[1][dr][1] && disk_shape[0][(dl + 0) % 7][3] <= disk_shape[1][dr][0])
               s[0] = 'D', st_map[dl][dr][0] = 1;
            if (disk_shape[0][(dl + 6) % 7][2] <= disk_shape[1][dr][1] && disk_shape[0][(dl + 6) % 7][3] <= disk_shape[1][dr][0])
               s[1] = 'U', st_map[dl][dr][1] = 1;
            if (disk_shape[0][dl][0] >= disk_shape[1][(dr + 0) % 7][3] && disk_shape[0][dl][1] >= disk_shape[1][(dr + 0) % 7][2])
               s[2] = 'R', st_map[dl][dr][2] = 1;
            if (disk_shape[0][dl][0] >= disk_shape[1][(dr + 6) % 7][3] && disk_shape[0][dl][1] >= disk_shape[1][(dr + 6) % 7][2])
               s[3] = 'L', st_map[dl][dr][3] = 1;
            //*/
            // 同向
            //*
            if (disk_shape[0][(dl + 0) % 7][3] <= disk_shape[1][dr][1] && disk_shape[0][(dl + 0) % 7][2] <= disk_shape[1][dr][0])
                s[0] = 'D', st_map[dl][dr][0] = 1;
            if (disk_shape[0][(dl + 6) % 7][3] <= disk_shape[1][dr][1] && disk_shape[0][(dl + 6) % 7][2] <= disk_shape[1][dr][0])
                s[1] = 'U', st_map[dl][dr][1] = 1;
            if (disk_shape[0][dl][0] >= disk_shape[1][(dr + 0) % 7][2] && disk_shape[0][dl][1] >= disk_shape[1][(dr + 0) % 7][3])
                s[2] = 'R', st_map[dl][dr][2] = 1;
            if (disk_shape[0][dl][0] >= disk_shape[1][(dr + 6) % 7][2] && disk_shape[0][dl][1] >= disk_shape[1][(dr + 6) % 7][3])
                s[3] = 'L', st_map[dl][dr][3] = 1;
            //*/
            printf("%4s,", s);
        }
        puts("");
    }
}

int main()
{
    genmap();
    return 0;
}

于是UD对应disk a的操作，LR对应disk b的操作