递归列表更新错误 [网格中的机器人] Python

Question

我正在做这本书中的问题：

网格中的机器人：想象一个机器人坐在 r 行 c 列的网格的左上角。机器人只能向右和向下两个方向移动，但某些单元格 "off limits" 使得机器人无法踩到它们。设计一个算法，为机器人寻找一条从左上角到右下角的路径。

我写了一个解决方案，但它不正确。

我在辅助函数中打印出了路径。一切都是正确的，但是当它返回 path_through_grid() 函数时，它变成了别的东西。我不知道这里发生了什么。请帮忙~

下面是我写的代码：

def path_through_grid(grid):
  path = ["start"]
  helper(grid, 0, 0, path)
  print("final", path)
  if path[-1]=='end':
    return path
  else:
    return None

def helper(grid, r, c, path):
  print("start---", r, " - ", c, "path: ", path)
  if r == len(grid) or c == len(grid[0]):
    return
  if grid[r][c] == 1:
    return
  if r == len(grid)-1 and c == len(grid[0])-1:
    print("inside")
    path.append("end")
    return
  path.append("right")
  helper(grid, r, c+1, path)
  print("middle---", r, " - ", c, "path: ", path)
  if path[-1]=="end":
    print("inside 2", path)
    return
  path = path[:-1]
  print("after", path)
  path.append("down")
  helper(grid, r+1, c, path)
  print("end---", r, " - ", c, "path: ", path)

import unittest

class Test(unittest.TestCase):
  def test_path_through_grid(self):
    grid = [[0,1],
            [0,0]]
    self.assertEqual(path_through_grid(grid), ["start", "down", "right", "end"])

if __name__ == "__main__":
  unittest.main()

Answer 1

问题出在这一行：

path = path[:-1]

此处赋值给path，这是一个错误。你应该只改变 path，而不是分配给它。当您分配时，调用者的 path 将不再受到影响——您现在已经创建了一个不同的列表引用。

因此，改用一种减小路径大小的方法

path.pop()

递归列表更新错误 [网格中的机器人] Python

List Update Error in a Recursion [Robot in a Grid] Python

python

algorithm

recursion

depth-first-search