|
Мифические шахматы
(Время: 1 сек. Память: 16 Мб Сложность: 42%)
Решение 1
Способ, которым воспользовалось большинство команд-участниц, заключался в рассмотрении всех вариантов расположения клеток относительно друг друга. Пусть клетка A – начальная позиция, а B – конечная. Тогда возможны следующие ситуации:
- A и B совпадают, тогда ответ 0;
- B - белая, тогда ответ -1;
- A и B - черные, тогда если они лежат на одной диагонали, то ответ 1, иначе 2;
- A - белая и B - черная, тогда необходимо проделать те же действия для восьми точек, в которые можно попасть конем, и выбрать минимальное значение.
Для определения цвета клетки с координатами (x,y) воспользуемся утверждением: если (x+y) нечетно, то клетка белая, иначе черная.
Решение 2
Для решения этой задачи можно воспользоваться волновым алгоритмом.
Сначала заполним массив -1, а в точку A поставим 0. А затем выполним три прохода (так как количество ходов не может быть больше трех) по массиву. Если в текущую клетку можно было попасть на предыдущем ходе, то необходимо отметить все клетки доски, в которые кентавр может попасть из этой клетки. Если текущая клетка белая, то выполняем ход коня (отмечаем 8 клеток, если они не выходят за границы доски и еще не отмечены). Если – черная, то отмечаем обе диагонали в обоих направлениях (с учетом аналогичных условий).
В результате заполнения доски вышеописанным образом в точке B мы будем иметь ответ на задачу.
Разбор: Кормышов М.Д.
| |
