Недавно мне понадобилось решить задачу поиска кратчайшего пути с клетки A в клетку B алгоритмически, и реализовать это программно. «Наверняка это уже тысячу раз кто-то делал и в интернете полно готовых решений». — подумал я, и каково же было мое разочарование… Несколько дней поисков ничего конкретного не дали. Максимум, что удалось найти, это упоминание, что решить данную задачу можно используя теорию графов и алгоритмом поиска в ширину (BFS — breadth first search). В этой статье я попробую подробно разобрать данный способ нахождения кратчайшего пути шахматных фигур с примерами кода и пояснениями.
Читать далее…