从并置在网格中查找最长的整数

Question

对于给定的矩阵，长度4的最长整数是9121

A = [
[9, 1, 1, 0, 7],
[1, 0, 2, 1, 0],
[1, 9, 1, 1, 0],
]
rows = 3
cols = 5

这是我的Python代码对于给定的行和列(i, j)我正在尝试找出长度为四的所有路径

def find_the_path(A, rows, cols, i, j):
    stack = []
    count = 0
    result = []
    seen = set()
    stack.append((i, j))
    while stack:
        if length(result) == 4:
            result = result[1:]
            seen.clear()

        x, y = stack.pop()
        result.append(A[x][y])
        seen.add(A[x][y])
        count += 1
        # Checking right, left, down, up
        # Trying to use stack, so that I can pop the last element
        # Storing the result in a list and checking for length 4
        for d in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            next_x, next_y = x + d[0], y + d[1]
            if 0 <= next_x < rows and 0 <= next_y < cols:
                if A[next_x][next_y] not in seen and length(result) < 4:
                    stack.append((next_x, next_y))
                    # result.append(A[next_x][next_y])
                    seen.add(A[next_x][next_y])
                    count += 1
                if length(result) == 4:
                    print(result)
                    break

我不确定为什么不打印[0,1]中的元素

上面的代码打印

9,1,1,9
1,1,9,0
1,9,0,1

我花了很多时间在Google上，但无法完成此操作。我不需要代码，我需要一种解决方法。

Answer 1

Python禅的一行（在python终端中为import this类型，是]

简单胜于复杂。

您尝试进行深度优先搜索。深度优先搜索是一种递归算法。通常，您可以通过两种方式实现递归算法：过程式和递归。

我认为过程方法较复杂，但通常具有更好的性能，并且比递归方法受内存的限制少。

以我的经验，python中的递归方式更易于读写。但是它更多地受到程序存储方式的限制。

因为您只看了4个步骤，所以我认为使用递归方法更容易。

---

您的实现有时使用点（(x, y)），有时使用值（1）。如果使用点来构建路径，然后创建一条新路径来存储值而不是准备好返回的点，则实现会更简单。

---

您在算法中构造的近邻点（next_x，next_y）。我会将那部分放在单独的函数中。

def neigbours(x, y, rows, cols):
    for rel_x, rel_y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        next_x, next_y = x + rel_x, y + rel_y
        if 0 <= next_x < rows and 0 <= next_y < cols:
            yield next_x, next_y

# so that you can do the following
rows, cols = 3, 5
x, y = 0, 0
for next_x, next_y in neigbours(x, y, rows, cols):
    print(next_x, next_y)

# output
0 1
1 0