Поиск пути на 2D карте с python - PullRequest
Новая
       38

Поиск пути на 2D карте с python

0 голосов
/ 25 марта 2020

Мне дали лабиринт в виде карты меток (пиксель матрицы имеет значение 1 или 0). Я не могу пересечь пиксели со значением 0. Учитывая начальную точку (x1, y1) и конечную точку (x2, y2), я должен найти все возможные пути между двумя точками, используя python. Есть ли способ сделать это? Есть ли алгоритм, который позволяет мне находить ВСЕ возможные пути и сохранять их?

Спасибо!

1 Ответ

0 голосов
/ 25 марта 2020

Следующий Python код, основанный на изменении подпрограммы C ++ для подсчета путей.

Код 

# Check if cell (x, y) is valid or not
def is_valid_cell(x, y, N):
    if x < 0 or y < 0 or x >= N or y >= N:
        return False

    return True

def find_paths_util(maze, source, destination, visited, path, paths):
  """Find paths using Breadth First Search algorith """
  # Done if destination is found
  if source == destination:
    paths.append(path[:])  # append copy of current path
    return

  # mark current cell as visited
  N = len(maze)
  x, y = source
  visited[x][y] = True

  # if current cell is a valid and open cell, 
  if is_valid_cell(x, y, N) and maze[x][y]:
    # Using Breadth First Search on path extension in all direction

    # go right (x, y) --> (x + 1, y)
    if x + 1 < N and (not visited[x + 1][y]):
      path.append((x + 1, y))
      find_paths_util(maze,(x + 1, y), destination, visited, path, paths)
      path.pop()

    # go left (x, y) --> (x - 1, y)
    if x - 1 >= 0 and (not visited[x - 1][y]):
      path.append((x - 1, y))
      find_paths_util(maze, (x - 1, y), destination, visited, path, paths)
      path.pop()

    # go up (x, y) --> (x, y + 1)
    if y + 1 < N and (not visited[x][y + 1]):
      path.append((x, y + 1))
      find_paths_util(maze, (x, y + 1), destination, visited, path, paths)
      path.pop()

    # go down (x, y) --> (x, y - 1)
    if y - 1 >= 0 and (not visited[x][y - 1]):
      path.append((x, y - 1))
      find_paths_util(maze, (x, y - 1), destination, visited, path, paths)
      path.pop()

    # Unmark current cell as visited
  visited[x][y] = False

  return paths

def find_paths(maze, source, destination):
  """ Sets up and searches for paths"""
  N = len(maze) # size of Maze is N x N

  # 2D matrix to keep track of cells involved in current path
  visited = [[False]*N for _ in range(N)]

  path = [source]
  paths = []
  paths = find_paths_util(maze, source, destination, visited, path, paths)

  return paths

Тест 

# Test Maze
maze = [
  [1, 1, 1, 1],
  [1, 1, 0, 1],
  [0, 1, 0, 1],
  [1, 1, 1, 1]
]
N = len(maze)

# Start point and destination
source = (0, 0)  # top left corner
destination = (N-1, N-1)  # bottom right corner

# Find all paths
paths = find_paths(maze, source, destination)

print("Paths with '->' separator between maze cell locations")
for path in paths:
  print(*path, sep = ' -> ')

Выход 

Paths with '->' separator between maze cell locations
(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)
(0, 0) -> (1, 0) -> (1, 1) -> (0, 1) -> (0, 2) -> (0, 3) -> (1, 3) -> (2, 3) -> (3, 3)
(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)
(0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (1, 3) -> (2, 3) -> (3, 3)
...