蜗牛算法 - 控制遍历的最大/最小位置

Question

我正在 CodeWars 中解决一个问题，只是为了好玩，但我遇到了一些问题：

1. 了解我需要在哪里修改代码，以便正确控制 m 和 n 的“转折点”，使它们开始减少而不是增加。

2. 适当重构此代码。

该算法的目的是像“蜗牛”一样遍历一个2D列表，例如

    [[1,2,3],
     [4,5,6],
     [7,8,9]]

应该返回

[1,2,3,6,9,8,7,4,5]

对于任何大小为 n*n 的列表

我在数学或计算机科学方面没有很强的背景，但我真的很喜欢两者，并尝试深入理解这些问题。

例如，我知道，如果n表示 2D 列表的行和m列，我需要n 为蜗牛的每个“电路”将最小值增加 1，并减少m每个电路的最大值，但我有很难理解需要在哪里发生。

我简要地研究了一些递归解决方案，但在开始深入研究这些解决方案之前，我希望有人可以看看这个并帮助我理解我的想法在哪里完全错误。

    [[1,2,3],
     [4,5,6],
     [7,8,9]]

该算法在 3x3 2D 列表上的输出是 current [1, 2, 3, 6, 9, 8, 7, 4, 5, 4]，这意味着我在到达末尾后向后移动。

在更大的 4x4 二维列表中，

array = [[1,2,3,4],
         [4,5,6,7],
         [8,9,10,11],
         [12,13,14,15]]

输出是[1, 2, 3, 4, 7, 11, 15, 14, 13, 12, 8, 4, 5, 4, 5, 4]，所以我在第一行来回移动。

感谢您的阅读，我希望这符合 SO 问题的指导方针。我不太关心在练习中获得分数/是否正确，而更关心理解为什么我的代码是错误的/实践不佳。

更新

我相信，我对这个问题有了更好的理解，并且已经取得了一些进展，但让我丧命的仍然是列表的界限。我感觉我在这方面真的很弱。我最终在一个方向上走得太远了，而我所有的解决方案都非常笨拙。

[1,2,3,6,9,8,7,4,5]

Answer 1

我只是提供一个想法，代码应该由你自己编写。

蜗牛有四个方向，依次为右（j += 1）、下（i += 1）、左（j -= 1）、上（i -= 1）。

蜗牛会沿着圆圈上的这四个方向（右、下、左、上、右、下、左...），转向下一个方向直到到达边界或访问过的数字。当蜗牛无法走到任何格子时结束。

定义can not walk to any grid：不能进入该方向和下一个方向的下一个网格。

带注释的示例代码

directions = [
    lambda i, j: (i, j + 1),
    lambda i, j: (i + 1, j),
    lambda i, j: (i, j - 1),
    lambda i, j: (i - 1, j),
]

array = [[1,2,3,4],
         [4,5,6,7],
         [8,9,10,11],
         [12,13,14,15]]

def in_matrix(i, j):
    return 0 <= i < len(array) and 0 <= j < len(array)

def is_visited(i, j):
    return array[i][j] == 0


def snail(array):
    direction_cnt = 0
    i, j = 0, 0
    ret = []
    ret.append(array[i][j])
    array[i][j] = 0  # mark as visited
    while True:
        direction_func = directions[direction_cnt % 4]  # turning directions in circle
        tmp_i, tmp_j = direction_func(i, j)  # attempt to head one step
        if (not in_matrix(tmp_i, tmp_j)) or is_visited(tmp_i, tmp_j):  # over border or visted
            direction_cnt += 1  # change direction
        else:
            i, j = tmp_i, tmp_j  # confirm this step
            ret.append(array[i][j])
            array[i][j] = 0  # mark as visited
            if len(ret) == len(array)**2:  # simple terminal criteria
                return ret


if __name__ == '__main__':
    print snail(array)