5

我的问题与八皇后谜题非常相似。

例如，我有一个二维数组（N x N），如下所示：

0,0,0,0,1 y
0,0,0,0,0 |
0,0,0,0,0 V
0,0,0,1,0
0,0,0,0,0
x->

我正在水平、垂直和对角线检查 1 的出现

\,0,|,0,/
0,\,|,/,0
-,-,1,-,-
0,/,|,\,0
/,0,|,0,\

我正在考虑仅将“1”的（x，y）位置存储在列表中

[[4,0],[3,3]]

并以数学方式解决它，用另一个 (x1,y1)<->(x2,y2) 检查“1”的每个位置，

如果x1 == x2或y1 == y2 we have a collision!如果不检查：

x2 == x1 + z;
y2 == y1 + z;
x2 == x1 - z;
y2 == y1 - z;

（？？？）

其中z是+/-( x1+z in 0..N ) and ( y1+z in 0..N ) .......

我的问题是检查对角线碰撞，有更好的方法吗？？？

4

4 回答 4

20

一种可能的解决方案：

def collision(x1, y1, x2, y2):
    return x1 == x2 or y1 == y2 or abs(x1-x2) == abs(y1-y2)

即如果两个点在同一水平行、同一垂直行或同一对角线（垂直距离==水平距离）上，则会发生碰撞。

于 2008-12-21T20:10:32.123 回答
2

您的描述听起来像是一个精确覆盖问题的实例，可以使用 Knuth 调用Algorithm X的算法来解决。我已经使用这种技术在 Javascript 中实现了数独求解器。你也可以在 Python 中找到实现。

于 2008-12-21T21:06:14.163 回答
0

我认为如果你不从数学上解决它会快得多，而是首先检查所有行是否多次出现 1，然后检查所有列，最后检查所有对角线。

这是一些以简单方式测试对角线的代码。（这是 JavaScript，对不起！）

var count = 0;
for (column = -n; column < n; column++) {
    for (row = 0; row < n; row++) {
            // conditions for which there are no valid coordinates.
            if (column + row > 6) {
                break;
            }
            if (column < 0) {
                continue;

            if (field[row][column] == 1) {
                count++;
                if (count == 2)
                    break; // collision
            }
    }
}

这种方法的复杂度为O(n^2)，而您建议的方法的复杂度为O(n^2 + k^2)（k 是 1 的数量）如果k总是很小，这应该没问题。

于 2008-12-21T20:31:52.610 回答
0

假设你确实有一个 N 维空间，你可能没有，你可以使用这个碰撞检测器：

def collision(t1, t2):
    return len(set([abs(a-b) for a,b in zip(t1, t2)] + [0])) <= 2

向它传递一对你喜欢的元组，如果这两个点位于任何 N 维对角线上，它将返回 true。

于 2008-12-22T04:01:08.943 回答