Практика программирования (Бейсик, Си, Паскаль)



         

Задачи, советы и ответы - часть 7


Для определения минимального количества ходов, соединяющих клетки a[i1,j1] и a[i2,j2], предлагается следующий алгоритм. Сначала все элементы массива расписываются каким-то кодом, например числом — 1, означающим, что все клетки шахматного поля свободны. Затем в начальную позицию a[i1,j1] заносится 0 и делаются попытки определить все клетки, достижимые за один ход. В каждую из них заносим 1. Для каждой клетки, достигаемой после первого хода, делается попытка совершить следующий ход, и все вновь достигаемые позиции метятся кодом 2. Естественно, что среди них исключаются ходы, возвращающие нас в начальную позицию, т. е. ходить надо только по свободным клеткам. Из каждой клетки, достигаемой за два хода, делается попытка совершить следующий ход в еще не занятые позиции и пометить все допустимые элементы массива числом 3. Числовую метку, которую мы заносим на очередном шаге охвата клеток шахматного поля, можно назвать уровнем досягаемости.

Расстановка уровней досягаемости продолжается до тех пор, пока мы не попадем в конечную позицию а [12, j2]. А еще лучше — до тех пор, пока не будет заполнена вся матрица, и тогда мы получим ответ, за сколько ходов можно переместиться из позиции a [i1, j1] в любую другую клетку шахматного поля.

Наряду с матрицей а можно ввести еще один массив ь и заполнять его аналогичным образом, начиная из конечной позиции b[i2,j2]. Если n-минимальное число ходов, переводящих коня из клетки a[i1, j1] в клетку а [i2, j2], то обратное путешествие по минимальной траектории займет тоже п шагов. Кроме того, можно заметить, что в каждой клетке любой минимальной траектории имеет место равенство

a[i,j] + b[i,j] = n.

Оно означает, что число промежуточных ходов из начальной позиции в клетку a [i, j ] и число встречных ходов по этой же траектории из конечной точки в сумме составляют длину минимальной траектории. Этот факт позволяет отсечь все недопустимые позиции и, тем самым, выделить клетки, принадлежащие только минимальным траекториям.

В качестве программы, доведенной до конца, мы ограничимся формированием всех уровней досягаемости из заданной позиции и по результатам ее работы узнаем, что любая клетка шахматного поля может быть достигнута не более чем за шесть ходов.




Содержание  Назад  Вперед