我尝试编写一个递归函数，它接受一组整数数组，并返回从左上角到右下角的路径，仅在相邻单元格之间传递，其中每个新单元格必须大大大于前一个单元格。
为了获得准确的路线，我需要按以下顺序检查四个相邻的单元格：右、下、左和上。
def exit_rectangle_position(array, row, col, l):
if col + 1 < len(array) and array[row][col+1] > array[row][col]:
l.append([row,col+1])
exit_rectangle_position(array, row, col+1, l)
elif row + 1 < len(array) and array[row+1][col] > array[row][col]:
l.append([row+1,col])
exit_rectangle_position(array, row+1, col, l)
elif col - 1 >= 0 and array[row][col-1] > array[row][col]:
l.append([row,col-1])
exit_rectangle_position(array, row, col-1, l)
elif row - 1 >= 0 and array[row - 1][col] > array[row][col]:
l.append([row-1,col])
exit_rectangle_position(array, row-1, col, l)
def exit_rectangle(array):
l = []
l.append([0,0])
exit_rectangle_position(array,0,0,l)
if [len(array)-1, len(array)-1] in l:
return l
return []
问题是，当我卡住时，我不知道如何从我开始的地方回来。例如数组
print(exit_rectangle([[1,2,3],[2,0,5],[3,4,5]]))
我得回去
# [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]]
但我明白
# []
递归DFS在这里工作得很好：
def exit_rectangle(a, x=None, y=None, seen=None):
if x is None:
x = 0
if y is None:
y = 0
if seen is None:
seen = set()
if x + 1 == len(a[0]) and y + 1 == len(a):
# Exit found
return [(x, y)]
# Maybe we've been here before
if (x, y) in seen:
return None
seen.add((x, y))
# Go right
if x + 1 < len(a[0]) and a[y][x] < a[y][x+1]:
path = exit_rectangle(a, x+1, y, seen)
if path is not None:
return [(x, y)] + path
# Go left
if 0 < x and a[y][x] < a[y][x-1]:
path = exit_rectangle(a, x-1, y, seen)
if path is not None:
return [(x, y)] + path
# Go up
if 0 < y and a[y][x] < a[y-1][x]:
path = exit_rectangle(a, x, y-1, seen)
if path is not None:
return [(x, y)] + path
# Go down
if y + 1 < len(a) and a[y][x] < a[y+1][x]:
path = exit_rectangle(a, x, y+1, seen)
if path is not None:
return [(x, y)] + path
# Dead end
return None
print(exit_rectangle([[1,2,3],[2,0,5],[3,4,5]]))
