JS: с учетом точки в двумерном массиве и расстояния, какие координаты можно перемещать? - PullRequest
Новая
       36

JS: с учетом точки в двумерном массиве и расстояния, какие координаты можно перемещать?

4 голосов
/ 07 декабря 2010

Имеется двумерный массив любого размера, например: 

var board = [
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]
];

... и заданная точка [y] [x] в этом массиве, например: 

board[3][4]

... и определенное количество пробелов, которые он может перемещать (вверх / вниз / влево / вправо, не по диагонали), например: 

var distance = 3;

... как бы функция перебрала 2D массив и создала список только тех координат , по которым можно пройти?

(Вот наглядный пример заданной координаты (*) в массиве и окружающих перемещаемых координат.) 

0 0 0 0 0 0 0 0
0 0 0 3 0 0 0 0
0 0 3 2 3 0 0 0
0 3 2 1 2 3 0 0
3 2 1 * 1 2 3 0
0 3 2 1 2 3 0 0
0 0 3 2 3 0 0 0
0 0 0 3 0 0 0 0

Ссылка: JS: как алгоритмически выделить ромбовидную выборку координат x / y? (Я задавал этот вопрос раньше, но не могу понять, как ввести координату и получить список координат)

Ответы [ 3 ]

3 голосов
/ 07 декабря 2010

Итерация по всем координатам (или подмножеству x-d,y-d ... x+d,y+d, если область большая).

Для каждого из них рассчитайте расстояние - в вашем случае как dx - dy - и всякий раз, когда вы найдете точку с расстоянием> 0, делайте с ней все, что хотите. В противном случае игнорируйте это. Вот и все!

По сравнению с подходом с флуд-заливкой вы получаете простой код без дополнительных таблиц поиска.

1 голос
/ 07 декабря 2010

Это самое простое решение, которое я могу придумать, оно включает в себя работу сверху вниз и слева направо, итерируя по только те координаты, которые допустимы , поэтому оно должно быть довольно быстрым: 

function getPossibleMoves(x, y) {
    var r, c, cMax, 
        distance = 3,
        rows = board.length,
        cols = board[0].length, 
        rMax = Math.min(y + distance + 1, rows),
        ret  = [],
        yOff;

    // Start at the first row with a permissible move
    for (r = Math.max(y - distance, 0); r < rMax; r++) {
        yOff = Math.abs(r - y);

        // Work out where we should stop looping for this row
        cMax = Math.min(x + distance - yOff + 1, cols);

        // Start at the first column with a permissible move
        for (c = Math.max(x - distance + yOff, 0); c < cMax; c++) {
            // If it's not the current position, add it to the result
            if (x != c || y != r)
                ret.push([c, r]);
        }
    }
    return ret;
}

Чтобы дать вам лучшее представление, я собрал демонстрационную версию, которая позволяет вам настраивать все различные переменные, например, размер доски, расстояние и т. д.

Рабочая демоверсия: http://jsfiddle.net/AndyE/fWDHy/2/

0 голосов
/ 07 декабря 2010

Использовать рекурсию вместе со списком / хэшем посещенных ссылок. Сделайте шаг, уменьшите вашу способность путешествовать на единицу и передайте список того, что вы видели. Добавьте ваше текущее местоположение в список посещенных мест. Идите в каждом направлении по одному шагу (используя рекурсию), передавая значение «влево», которое на единицу меньше, чем вам было дано.

Вот ответ, который почти работает ; Единственная проблема заключается в том, что он никогда не посещает камеру, даже если для ее достижения использовался долгий путь. Вы можете преодолеть это либо с помощью поиска в ширину , либо обнаружив, что посещенная ячейка была достигнута с помощью большего количества шагов, чем вы собираетесь предпринять, чтобы попасть туда.

...