所以我正在接受foo.bar挑战并需要准备兔子逃脱 . 每当我在我的代码上运行测试用例时它都可以工作，但仍然说提交时失败了 .
挑战是通过矩阵迷宫m x n获得最短路径，其中2 <m，n <20并且可以移除一个壁 .
我的解决方案是从一开始就找到完成所有可能的路径，计算沿途穿过的墙数 . 如果墙的数量为1或更少，则解决方案有效并记录其长度 .
path_dict = {}
min_solution = None
def answer(maze):
path = None
traverse (maze, path, 0, 0)
global min_solution
return min_solution
def traverse (maze, path, x, y):
global path_dict
global min_solution
cell_str = '(%d,%d)' % (x, y)
x_max = len (maze) - 1
y_max = len (maze[0]) - 1
# check x and y are valid
if x < 0 or x > x_max:
return
if y < 0 or y > y_max:
return
# Check not already visited cell
if path and cell_str in path:
return
total = None
if path:
total = path_dict [path]
f_cell = '(%d,%d)' % (x_max, y_max)
if path and f_cell in path:
return
# Check if final cell
if x == x_max and y == y_max:
if not path [-5:] == f_cell:
path += f_cell
path_dict [path] = total
solution_len = len (path.split (')('))
if not min_solution:
min_solution = solution_len
elif solution_len < min_solution:
min_solution = solution_len
#maze [x][y] = 2
return
#if path and path [-5:] == f_cell:
# return
# Not final cell - get value, add to count
# Add path string to mem
if path:
path += cell_str
cell_val = maze [x][y]
total += cell_val
# too many walls hit, stop checking this path
if total >= 2:
return
else:
path = cell_str
total = 0
path_dict [path] = total
if min_solution and len (path.split (')(')) > min_solution:
return
# Move DOWN, RIGHT, UP, LEFT
traverse (maze, path, x + 1, y)
traverse (maze, path, x, y + 1)
traverse (maze, path, x - 1, y)
traverse (maze, path, x, y - 1)
return