Skip to main content
 首页 » 编程设计

python之在python中递归退出矩形

2024年11月24日9xiaohuochai

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

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

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