НачалоДругие разделы
Дата и время
20/12/2024 06:13:36
Занятие 24
1. Ход конем
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 07/05/2008 | Занятие 24 (1) |
Ограничения: время – 4s/8s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
На шахматной доске `M`x`N` стоит белый конь и две черные фигуры. На одной клетке не может находиться более одной фигуры. Какое минимальное количество ходов должен сделать конь для достижения целевой клетки? Конь не может становиться под бой черных фигур, но может сбивать их в процессе очередного хода. Черные фигуры неподвижны.
Ввод содержит размеры шахматной доски `M`, `N` (`3\ ≤\ M,\ N\ ≤\ 1000`), затем две тройки чисел – код черной фигуры (1 – король, 2 – ферзь, 3 – ладья, 4 – конь, 5 – слон) и ее координаты, затем две пары чисел – начальное и конечное положение коня.
Выведите искомое минимальное количество ходов. Если провести коня невозможно, вывести –1.
Пример ввода
7 9 5 2 4 2 5 6 6 2 2 9
Вывод для примера
5
