Задача 05-4. Два коня
(Разбор)
Постороим граф, вершиной в котором будет пара клеток доски, задающая положение коней. Ребром соединим вершины, в которые можно попасть за один ход Красного и Зеленого коня. Чтобы найти ответ к задаче, нужно найти в графе кратчайшее расстояние от вершины, соответствующей начальному положению коней на доске до любой из вершин, задающих две одинаковые клетки доски. Будем решать эту задачу поиском в ширину. Заметим, что вершину графа можно задавать одним числом A*1000+B*100+C*10+D, где A и B будут координатами первого коня на доске,а C и D - второго. Как и в предыдущих задачах, сам граф с ребрами хранить не надо. Поиск соседей вершины осуществляется аналогично задаче 2, только здесь нужно будет смещать положение обоих коней одновременно. Как только мы нашли вершину, первые две цифры которой совпадают со вторыми двумя, поиск закончен, ответом будет номер шага, на котором получена эта вершина.
[an error occurred while processing the directive]