Проверка 2-мерного массива (как головоломка восьми королев) - PullRequest
Новая
       20

Проверка 2-мерного массива (как головоломка восьми королев)

5 голосов
/ 21 декабря 2008

Моя проблема очень похожа на головоломку «Восемь королев».

У меня есть 2-мерный массив (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,\

Я думаю о сохранении только (x, y) позиций "1" в списке 

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

и, решая ее математически, проверяйте каждую позицию «1» с другой (x1, y1) <-> (x2, y2),

если 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 ]

20 голосов
/ 21 декабря 2008

Одно из возможных решений: 

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

т.е. есть столкновение, если две точки находятся в одном и том же горизонтальном ряду, одном и том же вертикальном ряду или одной диагонали (вертикальное расстояние == горизонтальное расстояние).

2 голосов
/ 22 декабря 2008

Ваше описание звучит как пример точной проблемы покрытия, которая может быть решена с помощью алгоритма, который Кнут называет Алгоритм X . Я реализовал Решатель Судоку в Javascript , используя эту технику. Вы также можете найти реализации в Python.

0 голосов
/ 22 декабря 2008

Предполагая, что у вас действительно есть N-мерное пространство, которого у вас, вероятно, нет, вы можете использовать этот детектор столкновений: 

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

Передайте ему пару кортежей с любым значением арности, которое вам нравится, и он вернет true, если две точки лежат на любой N-мерной диагонали.

0 голосов
/ 21 декабря 2008

Я думаю, что было бы намного быстрее, если бы вы не решили математически, но сначала проверите все строки на предмет множественных вхождений 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 всегда мало, это не должно быть проблемой.

...