python - 在python中递归退出矩形

标签 python recursion

我尝试编写一个递归函数,它接受一组整数数组并返回从左上角到右下角的路径,仅在相邻单元格之间传递,其中每个新单元格必须比前一个单元格大得多.

为了获得准确的路线,我需要按以下顺序检查四个相邻的单元格:右、下、左、上。

enter image description here

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]]))

关于python - 在python中递归退出矩形,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56211824/

相关文章:

c - 使用 STATIC INT 进行阶乘程序

r - 使用堆算法生成排列

python - Django dateutil ISO 8601 没有 'read' 属性错误

python - 将 varargin 和 nargin 从 Matlab 转换为 Python

Python scikit学习MLPClassifier "hidden_layer_sizes"

javascript - django 形成一个弹出对话框

algorithm - 在非图行中找到所有可能解决方案的递归算法

algorithm - Mergesort - 递归调用的最大数量

c++ - 使用 std::unique_ptr 的递归函数内存泄漏

python - 获取Python子进程中终端内执行的命令的进程ID