Блог

 def path(given_map, x, y):  x = given_map[0][0]   y = given_map[0][0]  cnt = 0   if x == len(given_map) and y == len(given_map):  cnt  = 1  return cnt   else:  if x lt; len(given_map) and y lt; len(given_map):  return path(given_map, x, y)    elif x lt; len(given_map) and y == len(given_map):  return path(given_map, x, y)    elif x == len(given_map) and y lt; len(given_map):  return path(given_map, x, y)  else:  cnt = 0  return cnt   if __name__ == '__main__':  input_map = [[1,2,9,4,9],  [1,5,8,7,9],   [9,3,9,9,2],   [2,3,7,5,9],   [1,9,9,1,0]]  print(path(input_map, 0, 0))   input_map = [[1,1,2],   [1,2,2],   [1,2,0]]  print(path(input_map, 0, 0))  

Список n*n должен быть введен для создания функции, которая возвращает количество путей, которые могут пройти от начальной точки [0][0] до конечной точки [n-1][n-1].

Движение может быть сделано только вниз и вправо, и может быть перемещено только в одном направлении по номеру, указанному в соответствующих координатах x и y.

Он не включает случаи за пределами карты после перемещения.

Приведенный выше код реализован настолько, насколько это возможно в пределах моих возможностей. Как я могу изменить его, чтобы он функционировал нормально?

Если вам не требуется реализовать это с помощью рекурсии, я бы предложил подход BFS (Поиск по ширине) с использованием словаря для отслеживания позиций/количества, которых вы достигли на каждом шаге прогрессии:

 def path(M):  result = 0 # final result  bounds = range(len(M)) # inside map  paths = {(0,0):1} # one path at start  while paths: # spread counts  nextPos = dict() # track next positions  for (x,y),count in paths.items(): # extend positon/count  if x == y == len(M)-1: result  = count # capture final count  dist = M[x][y] # travel distance  if not dist: continue # no movement ...  for x2,y2 in [(x,y dist),(x dist,y)]: # travel down amp; right  if x2 in bounds and y2 in bounds: # propagate count  nextPos[x2,y2] = nextPos.get((x2,y2),0) count  paths = nextPos # next step on paths  return result   input_map = [[1,2,9,4,9],  [1,5,8,7,9],   [9,3,9,9,2],   [2,3,7,5,9],   [1,9,9,1,0]] print(path(input_map)) # 2  input_map = [[1,1,2],   [1,2,2],   [1,2,0]] print(path(input_map)) # 1  

Если вам требуется реализовать рекурсивный подход, функцию можно адаптировать следующим образом (возвращая сумму рекурсивных подсчетов путей), но тогда она больше не будет BFS:

 def path(M,x=0,y=0):  if x == y == len(M)-1: return 1 # goal reached  dist = M[x][y] # travel distance  if not dist: return 0 # no movement  bounds = range(len(M)) # inside map  return sum(path(M,x2,y2) for x2,y2 in [(x,y dist),(x dist,y)]  if x2 in bounds and y2 in bounds) # sum of paths