JS：给定二维数组中的一个点和一个距离，哪些坐标是可移动的？

Question

给定一个任意大小的二维数组，如下所示：

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坐标的菱形选择？ （我之前问过这个问题，但我不明白如何输入坐标并接收坐标列表）

Answer 1

迭代所有坐标（如果面积很大，则迭代子集 xd,yd ... x+d,y+d）。

对于其中的每个字段，计算距离 - 在您的情况下为 dx - dy - 每当您找到距离 > 的点时0，用它做任何你想做的事。否则，忽略它。就是这样！

与洪水填充方法相比，您可以获得简单的代码，并且没有额外的查找表的开销。

Answer 2

这是我能想到的最简单的解决方案，它涉及从上到下、从左到右的工作，仅迭代允许移动的坐标，所以它应该非常快：

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/

Answer 3

使用递归以及访问过的链接的列表/散列。迈出一步，将你旅行的能力降低一级，并传递你所看到的清​​单。将您当前的位置添加到访问过的地点列表中。向每个方向走一步（使用递归），传递一个比给定的值少 1 的“左步”值。

这是一个几乎有效的答案；唯一的问题是，即使经过很长的路才到达某个单元，它也永远不会重新访问该单元。您可以通过 广度优先搜索 或检测访问的单元格是否是通过比您将要采取的步骤更多的步骤来达到目标​​。