arrays - 算法在蜗牛二维数组中查找数字位置

Question

我有一个二维数组正方形大小。

比如:

(3x3)         (4x4)
1 2 3    or   1   2   3   4
8 9 4         12  13  14  5
7 6 5         11  16  15  6
              10  9   8   7

我正在尝试通过给出 value 和 array size 二维数组的 Y, X position 来找到解决方案.

例子:

>> find_y_x_in_snail(3, 4)
1, 2
# in a 3x3 array, search value 4
return y=1 x=2

我必须在二维数组中创建蜗牛并返回位置的唯一想法......不太好。

我找到了相反的算法here (第一个例子)

有什么想法吗？

Answer 1

你可以使用这个函数:

def find_y_x_in_snail(n, v):
    r = 0
    span = n
    while v > span:
        v -= span
        r += 1
        span -= r%2
    d, m = divmod(r,4);
    c = n-1-d
    return [d, d+v, c, c-v][m], [d+v-1, c, c-v, d][m] # y, x

说明

r 是“蛇”达到目标值所需的转角数。

span 是蛇的当前直线段中值的数量，即它以 n 开头strong>，并在下一个弯道后减小，并且在下一个弯道每隔一秒再次减小。

d 是蛇距离矩阵最近边的距离，即“缠绕”级别。

m 表示包含目标值的线段的 4 条边中的哪条边:

0:向上
1: 对
2:向下
3: 左

根据 m 从包含 4 个表达式的列表中获取一个值，每个表达式都针对相应的边进行定制:它定义了 y 坐标。 x 应用了类似的方法(但表达式不同)。