Алгоритм Ли или конь в лабиринте

Мне был нужен просто путь коня по шахматной доске, но не вот такой, и не полный обход доски конём, а волновой алгоритм поиска пути, он же алгоритм Ли, с учётом того, что конь не может прыгать через "препятствия" на доске.

По сути, если ходить не на соседнюю клетку, а ходом коня или ещё каким, надо просто изменить принцип выбора соседних элементов при поиске свободных клеток.

Но я сегодня эту задачу уже не доделаю, некогда, а вот не-помню-откуда-взявшийся проект на C++ (консоль Visual Studio 2015), реализующий алгоритм Ли для поиска пути по лабиринту, прикреплю. Соседство клеток там стандартное для игр - вверх, направо, вниз и налево.

Этот проект я и попытался быстро применить к решению задачи.

Вот такой была исходная картинка:

тестовый лабиринт

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

int R[rows][cols] = {
  { y, n, e, y, y, y, y, n, y, y, y, y, y, y, y }, //8
  { y, n, n, n, n, n, y, n, y, n, n, n, n, n, y },
  { y, n, y, y, y, n, y, n, y, y, y, n, y, y, y }, //7
  { y, n, y, n, y, n, y, n, n, n, y, n, y, n, n },
  { y, y, y, n, y, y, y, n, y, y, y, n, y, y, y }, //6
  { n, n, n, n, y, n, n, n, y, n, n, n, n, n, y },
  { y, y, y, y, y, n, y, y, y, n, y, y, y, y, y }, //5
  { y, n, n, n, n, n, y, n, n, n, y, n, y, n, n },
  { y, n, y, y, y, y, y, n, y, y, y, n, y, y, y }, //4
  { y, n, y, n, n, n, n, n, y, n, n, n, n, n, y },
  { y, y, y, y, y, n, y, y, y, n, y, y, y, y, y }, //3
  { y, n, n, n, y, n, y, n, n, n, y, n, n, n, n },
  { y, n, y, y, y, n, y, y, y, n, y, n, y, y, y }, //2
  { y, n, y, n, n, n, n, n, n, n, y, n, n, n, y },
  { y, y, s, n, y, y, y, y, y, y, y, y, y, y, y }  //1
  //A     B     C     D     E     F     G     Н
};
// y - проходимо, n - нет, s - начало, e - конец

Класс Pathfinder из приложенного проекта делает всё примерно так, как написано в Вики, для теста использовался показанный выше "конский" лабиринт, при преобразовании данных в формат программы он превратился в такой вот файл data.txt:

Horizontal: 15
Vertical: 15
013000010000000
011111010111110
010001010001000
010101011101011
000100010001000
111101110111110
000001000100000
011111011101011
010000010001000
010111110111110
000001000100000
011101011101111
010001000101000
010111111101110
002100000000000

При описании лабиринта применяются такие числа:

• 0 - пусто;
• 1 - препятствие;
• 2 - начало;
• 3 - конец.

По идее, решение нашего лабиринта - это путь b1 - a3 - b5 - c7 - a6 - c5 - d7 - b8, но так как мы ходили "по одной клетке", программа выдала вот что:

вывод приложения

 Скачать архив .zip с решением LeePathFinder для Visual Studio 2015 (5 Кб)

Не забудьте перед сборкой выбрать нужную конфигурацию Studio (x64 или x86).

15.04.2018, 16:20 [3129 просмотров]