4×3锁定模式 [英] 4 by 3 lock pattern

查看：139
本文介绍了4×3锁定模式的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我碰到这个<一href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4334"相对=nofollow>问题。

，询问计算的方法的特定长度的锁定模式可以在4×3网格制成的数目和遵循的规则。 可能有一些观点不能包括在路径

一个有效图案具有以下属性：

    使用点，这它的触摸首次（在绘制图案的顺序相同）的序列

  • 一个图案可以重新presented，图案从（1,1）将（2 ，2）是不一样的从（2,2的图案会）至（1,1）。

  • 对于每个连续两个点A和B再presentation的格局，如果线段连接A和B通过一些其他的点，这些点的顺序必须也并配有前， B，否则该模式将无效。例如重新presentation的图案其与（3,1）则（1,3）开始是无效的，因为该段通过（2,2）穿过其中并没有出现在之前重新presentation图案（ 3,1），以及正确的重新presentation这种模式是（3,1）（2,2）（1,3）。但图案（2,2）（3,2）（3,1）（1,3）是有效的，因为（2,2）出现之前（3,1）

  • 在重新presentation图案我们不提不止一次的相同点越多，即使图案将通过另一有效段再次触摸该点，而在图案中的每个段必须从去一个点到另一个点该模式没有触及之前，它可能会通过一些点，这已经出现的格局。

  • 的图案的长度是在重新presentation图案每隔两个连续点之间的曼哈顿距离的总和。两个点（X1，Y1）和（X2，Y2）之间的曼哈顿距离是| X 1 - X 2 | + | Y1 - Y2 | （其中，| X |表示x的绝对值）。

  • 一个模式必须触及至少有两点

我的方法是蛮力，遍历点，开始在点，并使用递归decremente长度，直到达到一个长度为零，则加1，组合的数量。

有没有一种方法来计算它的数学公式，或有更好的算法吗？

更新： 这里是我做了什么，它给出了一些错误的答案！我认为这个问题是在 isOk 的功能！ notAllowed 是不准点的全局位掩码。

 布尔isOk（INT I，诠释J，诠释二，诠释DJ，LL访问）{
    INT迷你=（I＆LT;二）我：迪;
    INT minj =（J＆LT; D​​J）？J：DJ;

    如果（绝对第（i-二）== 2＆安培;＆安培; ABS（J-DJ）== 2＆安培;＆安培;！GETBIT（参观，迷你+ 1，minj + 1））
        返回false;
    如果（二== I和＆安培; ABS（的J  -  DJ）== 2及！＆安培; GETBIT（参观，我，minj + 1））
        返回false;
    如果（二== I和＆安培; ABS（J-DJ）== 3及和放大器;！（GETBIT（参观，我，1）|| GETBIT（参观，我，2）））
        返回false;
    如果（DJ == J＆安培;＆安培;！无水（ⅰ - 二）== 2＆安培;＆安培; GETBIT（访问了，1，j））后
        返回false;

    返回true;
}

INT F（INT I，诠释J，LL参观，int类型l）{
    如果（升→1）返回0;
    短的放大器; RES = DP [i] [j]的[访问] [1];
    如果（RES！= -1）返回资源;
    RES = 0;
    如果（L == L）返回++资源;

    对于（INT迪= 0;二＆LT; GN ++二）{
        对于（INT DJ = 0; DJ＆LT; GM ++ DJ）{
            如果（GETBIT（notAllowed，二，DJ）|| GETBIT（参观，二，DJ）||！isOk（I，J，二，DJ，参观））
                继续;
            RES + = F（DI，DJ，setbit（参观，二，DJ），L + DIST（I，J，二，DJ））;
        }
    }
    返回水库;
}

解决方案

<一个href="http://stackoverflow.com/questions/22621174/calculate-possible-snake-passwords/22622326#22622326">My回答另一个问题的可适于这个问题为好。

让 F（I，J，走访，K）的方式来完成部分的图案，我们目前正处于节点（i，j）的数量，已经参观了在顶点设置的访问的和迄今已走过了的 K 的路径长度。我们可以重新present的访问的作为位掩码。

我们可以计算的 F（I，J，走访，K）的递归通过尝试所有可能的下一步行动，并应用DP重用子问题的解决方案：

  

F（I，J，走访，L）= 1

     

F（I，J，走访，K）= 0如果k>→

     

F（I，J，走访中，k）=总和（可能的行动（I'，J'）表示：f（I'，J'，访问了联合{（I'，J'）}，K ​​+ DIS（ （I，J），（I'，J'）））

可能的行动是那些跨越访问的顶点的一个数字，然后结束了univisited（而不是禁止的）之一。

如果ð的是一套禁止顶点，该问题的答案是

  

和（（I，J）不是在D：F（I，J，{（I，J）}，L））。

运行时是一样的东西O（X ^ 2 * Y ^ 2 * 2 ^（X * Y）*最大可能的长度）。我想最大的可能长度其实远低于的 1000 的。

更新：我实现了这个解决方案，它被录取了。我列举的可能的行动以下列方式：假设我们是点（I，J）的和已经访问过的顶点集的访问的。枚举所有不同的互质对（DX，DY）0℃= DX＆LT; X和0℃=镝＆其中; Y.然后找出最小K的P_k =（I + K * DX，J + K * DY）仍然是一个有效的网格点和P_k不在的访问的。如果P_k并不被禁止，这是一个有效举措。

最大可能的路径长度为39。

我使用的是大小的DP排列3 * 4 * 2 ^ 12 * 40来存储子问题的结果。

I came across this problem.

which asks to calculate the number of ways a lock pattern of a specific length can be made in 4x3 grid and follows the rules. there may be some of the points must not be included in the path

A valid pattern has the following properties:

  • A pattern can be represented using the sequence of points which it's touching for the first time (in the same order of drawing the pattern), a pattern going from (1,1) to (2,2) is not the same as a pattern going from (2,2) to (1,1).

  • For every two consecutive points A and B in the pattern representation, if the line segment connecting A and B passes through some other points, these points must be in the sequence also and comes before A and B, otherwise the pattern will be invalid. For example a pattern representation which starts with (3,1) then (1,3) is invalid because the segment passes through (2,2) which didn't appear in the pattern representation before (3,1), and the correct representation for this pattern is (3,1) (2,2) (1,3). But the pattern (2,2) (3,2) (3,1) (1,3) is valid because (2,2) appeared before (3,1).

  • In the pattern representation we don't mention the same point more than once, even if the pattern will touch this point again through another valid segment, and each segment in the pattern must be going from a point to another point which the pattern didn't touch before and it might go through some points which already appeared in the pattern.

  • The length of a pattern is the sum of the Manhattan distances between every two consecutive points in the pattern representation. The Manhattan distance between two points (X1, Y1) and (X2, Y2) is |X1 - X2| + |Y1 - Y2| (where |X| means the absolute value of X).

  • A pattern must touch at least two points

my approach was a brute force, loop over the points, start at the point and using recursive decremente the length until reach a length zero then add 1 to the number of combinations.

Is there a way to calculate it in mathematical equation or there is a better algorithm for this ?

UPDATE: here is what I have done, it gives some wrong answers ! I think the problem is in isOk function ! notAllowed is a global bit mask of the not allowed points.

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;
}

解决方案

My answer to another question can be adapted to this problem as well.

Let f(i,j,visited,k) the number of ways to complete a partial pattern, when we are currently at node (i,j), have already visited the vertices in the set visited and have so far walked a path length of k. We can represent visited as a bitmask.

We can compute f(i,j,visited,k) recursively by trying all possible next moves and apply DP to reuse subproblem solutions:

f(i,j, visited, L) = 1

f(i,j, visited, k) = 0 if k > L

f(i,j, visited, k) = sum(possible moves (i', j'): f(i', j', visited UNION {(i',j')}, k + dis((i,j), (i',j')))

Possible moves are those that cross a number of visited vertices and then end in an univisited (and not forbidden) one.

If D is the set of forbidden vertices, the answer to the question is

sum((i,j) not in D: f(i,j, {(i,j)}, L)).

The runtime is something like O(X^2 * Y^2 * 2^(X*Y) * maximum possible length). I guess the maximum possible length is in fact well below 1000.

UPDATE: I implemented this solution and it got accepted. I enumerated the possible moves in the following way: Assume we are at point (i,j) and have already visited the set of vertices visited. Enumerate all distinct coprime pairs (dx,dy) 0 <= dx < X and 0 <= dy < Y. Then find the smallest k with P_k = (i + k*dx, j + k*dy) still being a valid grid point and P_k not in visited. If P_k is not forbidden, it is a valid move.

The maximum possible path length is 39.

I'm using a DP array of size 3 * 4 * 2^12 * 40 to store the subproblem results.

这篇关于4×3锁定模式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
C/C++开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆