Решение Практика «Путь в лабиринте»
Оригинальное решение практики «Путь в лабиринте»
На этот раз в лабиринт с сокровищами попал Жадина! Лабиринт очень старый и все свободные клетки успели покрыться зарослями. Для каждой клетки лабиринта известна её трудность — количество сил, которые потратит Жадина на прохождение зарослей этой клетки.
После каждого шага силы Жадины уменьшаются на трудность клетки, в которую он шагнул. Когда силы заканчиваются, Жадина останавливается.
Посмотреть на лабиринты можно запустив проект:
- Выбрать лабиринт можно в меню States слева сверху.
- Цифры и яркость на клетках — это трудность.
Жадина хочет узнать, какое минимальное количество сил ему нужно потратить чтобы дойти от текущей клетки до какого-то из сундуков. Причём, он ещё не решил, какой из сундуков он хочет посетить, так что Жадина хочет узнать кратчайшее расстояние до каждого из сундуков.
Помогите Жадине найти кратчайшие пути до каждого из сундуков!
Для того, чтобы сдать задачу, в файле DijkstraPathFinder.cs реализуйте метод GetPathsByDijkstra. Ему на вход поступают: лабиринт, начальная позиция Жадины, список целей — клеток, до которых нужно найти кратчайшие пути. Он должен возвращать пути до всех целей в виде IEnumerable в порядке увеличения трудности пути до них. При этом вычислять пути он должен лениво, то есть не вычислять пути до далёких сундуков и не обрабатывать весь лабиринт, пока это не запросили из IEnumerable.
Описание лабиринта передаётся в метод в объекте типа State:
- в поле CellCost находится двумерный массив трудностей всех клеток (0 означает стену).
- есть методы, которые помогут проверить, что какая-то клетка является стеной или находится внутри лабиринта.
- там же есть свойство Chests, но в данной задаче вместо него используйте список целей, переданный в метод аргументом.
Все тесты в классе DijkstraPathFinder_Should должны завершиться успехом.
