FasterHarder: Akina, я лишь частично (очень частично) понял твое сообщение.
Как мне показалось, ты намекаешь на выигрышную стратегию, например для игрока №1. Выигрышная стратегия - стратегия, приводящая к победе, независимо от ходов противника (при безошибочной игре противника не всегда существует). Смысл ее в том, что игрок №1 "направляет" игрока №2 по нужному пути независимо от того, как сходит игрок №2.
Игроку №1 надо, чтобы расстояние до тупика было НЕЧЕТНЫМ (1, 3, 17, 9999 шагов и т.д.) или четным, если рассматривать случай, когда игрок №1 уже походил в какую-то вершину. Например, стоит игрок №1 в стартовой вершине, перед ним развилка на 173 смежных вершины. Ему нужно сходить в вершину, расстояние от которой до тупика четное число. Затем ходит игрок №2 - куда захочет. Игрок №1 снова выбирает из набора возможных путей ту вершину, расстояние до тупика которое четно и т.д. Т е игрок №1 постоянно "навязывает" свой путь независимо от того, куда сходил игрок №2. Все это хорошо, но ведь возможны случаи, когда ходит игрок №1 и перед ним стая вершин и у КАЖДОЙ вершины расстояние до тупика - нечетное число. Выбора как бы нет, но это не означает, что игрок №1 не может выиграть. Он может временно согласиться пройти по "неправильному" для него пути, а через несколько итераций снова задать свое направление.
Да, я понимаю, что в своем сообщении ты не это описывал), просто решил написать про выигрышную стратегию, которая здесь вот таким образом не применима.

Akina, я бы хотел провести декомпозицию алгоритма на подалгоритмы, т к мне не хватает ума все это охватить и понять сразу. И пусть будет неоптимально, просто бы хоть как-то понять. (хотя в задаче еще есть ограничение по времени 8-) , т е как бы намек на то, что метод грубой силы тут не нужен, хотя я не уверен, что без него вообще можно реализовать)
---------------------------------------------------------
Вот хотелось бы понять, насколько все это пригодится в решении (забыл сделать ремарку, что тупиков может быть больше одного, разумеется + из конкретной вершины можно проложить путь разной протяженности до разных тупиков):
1. Получение всех тупиков достижимых из заданной вершины. В этом может помочь DFS+стек (вроде стек, а не очередь, т к она для BFS вроде). В результате будет сформирован одномерный массив вершин в том или ином виде. Хотя структуры данных оч.важны тоже, разумеется - без них дело гиблым оказывается при кодировании)
2. Получить множество всех вершин, через которые может проходить какой-либо путь до какого-либо тупика
3. ДЛЯ КАЖДОЙ вершины из п.2 найти расстояние ДО КАЖДОГО тупика! Это двумерный массив, где по оси Ох, допустим откладываются тупики, по оси Oy - №вершины, а на пересечении - расстояние между ними (или можно просто true/false аля чет/нечет длина)

И вот владея этой информацией (из п.3) разве невозможно проанализировать победу игрока №1 или №2??
Например, есть стартовая вершина и ходит игрок №1. Он может "просмотреть" все возможные пути (конкретно расстояния) до каждого достижимого тупика из этой вершины. Проблема выбора остается, т к путей нечетной длины может быть несколько...непонятно какой взять... :unsure: ... а может ЛЮБОЙ)) навряд ли...

в общем пока я далек от глубоко понимания решения поставленной задачи. нужна помощь)

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845439