4×3锁模式

Question

我偶然发现了这个问题。

它要求在4x3网格中计算特定长度的锁模式的数量，并遵循规则。中可能有一些点不能包含在路径中

有效模式具有以下属性：

• 一个模式可以用它第一次接触的点的顺序来表示(按照相同的绘制模式的顺序)，从(1,1)到(2,2)的模式与从(2,2)到(1,1)的模式并不相同。
• 对于模式表示中的每两个连续点A和B，如果连接A和B的线段通过其他点，这些点也必须在序列中，并且在A和B之前，否则模式将无效。例如，以(3,1)然后(1,3)开头的模式表示无效，因为段通过(2,2)，而(2,2)在(3,1)之前没有出现在模式表示中，并且该模式的正确表示是(3,1) (2，2) (1,3)。但是模式(2,2) (3,2) (3,1) (1,3)是有效的，因为(2,2)出现在(3,1)之前。
• 在模式表示中，我们不会不止一次地提到相同的点，即使模式将通过另一个有效段再次触及这个点，而且模式中的每个段必须从一个点到另一个点，而这个点是模式之前没有触及的，它可能会经过一些已经出现在模式中的点。
• 模式的长度是模式表示中每两个连续点之间曼哈顿距离的总和。两个点(X1，Y1)和(X2，Y2)之间的曼哈顿距离是x_1-X2_x_2+_~_
• 一个图案必须至少触及两点。

我的方法是一种蛮力，在点上循环，从点开始，然后使用递归递减长度，直到长度达到零，然后将组合数加1。

在数学方程中是否有计算它的方法，或者有一个更好的算法？

更新：就是我所做的，它给出了一些错误的答案！我认为问题在于isOk函数！notAllowed是不允许点的全局位掩码。

bool isOk(int i, int j, int di,int dj, ll visited){
    int mini = (i<di)?i:di;
    int minj = (j<dj)?j:dj;

    if(abs(i-di) == 2 && abs(j-dj) == 2 && !getbit(visited, mini+1, minj+1) )
        return false;
    if(di == i && abs(j - dj) == 2 && !getbit(visited, i,minj+1) )
        return false;
    if(di == i && abs(j-dj) == 3 && (!getbit(visited, i,1) || !getbit(visited, i,2)) )
        return false;
    if(dj == j && abs(i - di) == 2 && !getbit(visited, 1,j) )
        return false;

    return true;
}

int f(int i, int j, ll visited, int l){
    if(l > L) return 0;
    short& res = dp[i][j][visited][l];
    if(res != -1) return res;
    res = 0;
    if(l == L) return ++res;

    for(int di=0 ; di<gN ; ++di){
        for(int dj=0 ; dj<gM ; ++dj){
            if( getbit(notAllowed, di, dj) || getbit(visited, di, dj) || !isOk(i,j, di,dj,  visited) )
                continue;
            res += f(di, dj, setbit(visited, di, dj), l+dist(i,j , di,dj));
        }
    }
    return res;
}

Answer 1

我对另一个问题的回答也可以适应这个问题。

设f(i，j，visited，k)当我们目前在节点(i，j)时，已经访问了所访问集合中的顶点，并且迄今为止已经遍历了k的路径长度，我们可以用位掩码来表示完成部分模式的方法的数目。

通过尝试所有可能的下一步步骤，我们可以递归地计算f(i，j，apply，k)，并应用DP重用子问题解决方案：

f(i，j，已访问，L) =1 f(i，j，访问，k) =0如果k>L f(i，j，visited，k) =和(可能的移动(i'，j')：f(i'，j'，已访问的UNION {(i'，j')}，k+ dis((i，j)，(i'，j‘)

可能的移动是那些跨越多个已访问的顶点，然后以一个单一访问(而不是禁止的)顶点结束。

如果D是一组禁止顶点，则问题的答案是

和((i，j)非D: f(i，j，{((i，j)}，L))。

运行时类似于O(X^2 * Y^2 * 2^(X*Y) *最大可能长度)。我想最大可能的长度实际上远低于1000。

更新：I实现了这个解决方案，并被接受了。我以以下方式列举了可能的移动:假设我们在点(i，j)，并且已经访问了所访问的顶点集。枚举所有不同的互斥对( dx，dy) 0 <= dx

最大可能路径长度为39。

我使用一个大小为3*4* 2^12 * 40的DP数组来存储子问题结果。

Answer 2

组合的几个属性可用于优化蛮力方法：

1. 使用镜像(水平、垂直或两者)，您可以为找到的每个镜像生成4个组合(水平或垂直线除外)。也许你可以只考虑从一个象限开始的组合。
2. 通常可以通过翻译(移动组合)生成相同长度的附加组合。