Решение задачи 5.
Идея решения основывается на использовании очереди. Вначале в очередь помещается элемент, определяющий исходное положение шахматного коня, а соответствующая клетка поля помечается как посещенная.
На каждом из следующих шагов алгоритма (пока очередь не пуста или не помечена конечная клетка) выполняются следующие действия.
Из очереди извлекается очередной элемент, который определяет некоторую позицию (x,y).
Находятся клетки в пределах поля, которые достижимы из (x,y) одним ходом шахматного коня, и которые еще не помечены.
Элементы, соответствующие найденным клеткам, помещаются в очередь, а клетки помечаются как посещенные.
При этом вначале все клетки должны быть непомечены, а метку желательно ставить такую, чтобы можно было восстановить путь между полями.
Для этого метку поля можно определить как позицию поля, из которой она была помечена.
|
