Блог

Главная - Вопросы по программированию - Получение всех путей в массиве

Получение всех путей в массиве

#algorithm

#алгоритм

Вопрос:

У меня есть список, структурированный следующим образом:

 s = [
  [
    [[0, 1, 1], [0, 0, 0]],
    [[0, 0, 1], [0, 1, 0]],
    [[0, 0, 0], [0, 1, 1]],
    [[1, 0, 0], [0, 0, 0]],
    [[0, 0, 0], [1, 0, 0]],
    [[1, 0, 0], [0, 0, 0]],
  ],
  [  
    [[1, 0, 0], [0, 0, 0]],
    [[0, 0, 0], [1, 0, 0]],
    [[0, 1, 1], [0, 0, 0]],
    [[0, 0, 1], [0, 1, 0]],
    [[0, 1, 0], [0, 0, 1]],
    [[0, 0, 0], [0, 1, 1]]
  ],
  # And so on
]

Для каждого элемента с первым индексом, s[0] , если второй подмассив, s[0][i][1] , совпадает с соответствующим первым элементом в s[1] , то у нас есть путь или часть пути. Это сложно, поэтому я приведу пример:

 s = [
  [
    [[0, 1, 1], *[0, 0, 0]*], <---- This goes to multiple possibilities
    [[0, 0, 1], [0, 1, 0]],
    [[0, 0, 0], [0, 1, 1]],
    [[1, 0, 0], [0, 0, 0]],
    [[0, 0, 0], [1, 0, 0]],
    [[1, 0, 0], [0, 0, 0]],
  ],
  [  
    [[1, 0, 0], [0, 0, 0]],
    [*[0, 0, 0]*, [1, 0, 0]], <- here
    [[0, 1, 1], [0, 0, 0]],
    [[0, 0, 1], [0, 1, 0]],
    [[0, 1, 0], [0, 0, 1]],
    [*[0, 0, 0]*, [0, 1, 1]] <- and here
  ],
  # And so on
]

Как я могу найти количество путей для каждого заданного элемента?

Комментарии:

1. Это проблема динамического программирования обхода графа DFS / BFS. Я надеюсь, что эти ключевые слова помогут вам найти ответ путем поиска. Вы можете использовать DFS / BFS для перехода от верхнего левого элемента к нижнему правому и использовать «кэш» или карту для записи количества путей в каждой позиции. Если эти слова для вас неясны или вы не смогли найти идеальных решений, вы можете прокомментировать здесь свои проблемы 🙂

2. Привет, Марк, спасибо. Я пытаюсь сделать это таким образом, но я просто борюсь. Я получу это, хотя в конце концов 🙂

3.Некоторые, возможно, полезные ссылки для вас: geeksforgeeks.org/check-possible-path-2d-matrix algorithms.tutorialhorizon.com /…

4. Требуется пояснение: что должно означать «и так далее»? Т.е. У вас есть путь только в том случае, если существует полный путь от s [0], поэтому s [n] где n — размер s, или вам просто нужны ссылки s [i] на s [i 1]? Кроме того, тройки отвлекают, с таким же успехом могут быть a, b, c, .. верно?