如何从中心向外以菱形模式遍历 (2n+1)(2n+1) 数组？

Question

1. 我该如何从数组的中心向外遍历，每个单元格只访问一次呢？

我可以通过广度优先遍历的方法，找到未访问的邻居来实现，但我想知道有没有什么方法可以用编辑距离的方式来遍历？我在纸上试着计算，但总是理不清楚。

比如，在一个数组中：

[
[5 6 8 9 0]
[1 2 4 5 6]
[5 4 0 2 1]
[1 2 3 4 5]
[1 2 3 4 5]]

从中心的零开始，我们会先访问坐标 [1][2] 的4，然后是坐标 [2][3] 的2，再接着是坐标 [3][2] 的3，然后是坐标 [2][1] 的4，接着是坐标 [0][2] 的8，最后是坐标 [1][3] 的5，依此类推。

我尝试过这种方法，虽然接近了，但还是遗漏了一些。

def traversalOrder(n): #n is size of array (always square)

    n = n/2
    t = []
    for k in range(1,n+1):
        t += [(i,j) for i in range(n-k,n+k+1) for j in range(n-k,n+k+1) if (i,j) not in t and (i-j == k or j-i == k)  ]

Answer 1

我觉得最简单的方法是用三个嵌套的循环。最外层的循环是用来处理你想要的钻石的扩展半径。接下来的循环是处理一个钻石的四条边，每条边由一个起始点和一个移动方向来描述。最里面的循环则是遍历那条边上的所有点。

def traversal(n):
    h = n//2
    yield h, h   # center tile doesn't get handled the by the loops, so yield it first
    for r in range(1, n):
        for x0, y0, dx, dy in [(h, h-r, 1, 1),
                               (h+r, h, -1, 1),
                               (h, h+r, -1, -1),
                               (h-r, h, 1, -1)]:
            for i in range(r):
                x = x0 + dx*i
                y = y0 + dy*i
                if 0 <= x < n and 0 <= y < n:
                    yield x, y

如果n总是奇数的话，你可以通过限制i来稍微提高内层循环的性能，而不是计算所有的点然后再进行边界测试来跳过那些在网格外的点。把range(r)改成range(max(0, r-h), max(r, h+1))，并且在yield之前去掉if语句就可以了。不过我还是保留上面的版本，因为它的逻辑更清晰。

Answer 2

看起来你可以用一种叫做优先队列的东西来根据编辑距离来排序元素，就像你提到的那样。虽然我的编辑距离可能不能给你想要的准确顺序，但这可以作为一个起点。我使用了heapq这个库。

import heapq

grid = [
[5, 6, 8, 9, 0],
[1, 2, 4, 5, 6],
[5, 4, 0, 2, 1],
[1, 2, 3, 4, 5],
[1, 2, 3, 4, 5]]

rows = len(grid)
cols = len(grid[0])

heap_list = []

for row in xrange(rows):
    for col in xrange(cols):
        edit_distance = abs(row - rows/2) + abs(col - cols/2)
        #heappush(heap, (priority, object))
        heapq.heappush(heap_list, (edit_distance, grid[row][col]))

for i in xrange(len(heap_list)):
    print heapq.heappop(heap_list)

# prints (distance, value)
# (0, 0)
# (1, 2)
# (1, 3)
# (1, 4)
# (1, 4)
# (2, 1)
# etc...

Answer 3

我有一个开源库pixelscan，它可以在网格上进行这种空间模式的遍历。这个库提供了各种扫描功能和坐标转换。例如，

x0, y0, r1, r2 = 0, 0, 0, 2
for x, y in ringscan(x0, y0, r1, r2, metric=manhattan):
    print x, y

其中

x0     = Circle x center
y0     = Circle y center
r1     = Initial radius
r2     = Final radius
metric = Distance metric

会生成一个菱形形状的点：

(0,0) (0,1) (1,0) (0,-1) (-1,0) (0,2) (1,1) (2,0) (1,-1) (0,-2) (-1,-1) (-2,0) (-1,1)

你可以通过平移来选择任何你想要的中心点开始。