Задача Queen
На обобщенной шахматной доске (размерами не обязательно 8×8)стоит ферзь. Известно, на какой клетке он находится сейчас и в какую клетку ему необходимо добраться. Задача усложняется тем, что некоторые клетки заняты фигурами соперника, но упрощается тем, что сейчас они крепко спят, так что ферзь может
тихонько сделать сколько угодно ходов подряд. Ни перепрыгивать через фигуры соперника, ни бить их нельзя (ибо тогда они проснутся). Напишите программу, определяющую минимальное количество ходов,
необходимых ферзю для такого перемещения.
Технические условия. Программа читает с клавиатуры размеры шахматной доски — сначала количество вертикалей w (2 ≤ w ≤ 26), затем количество горизонталей h (2 ≤ h ≤ 99), затем координаты стартовой и финишной клеток, затем количество фигур соперника К (0 ≤ K ≤ w×h–2),
далее K пар чисел – координаты очередной фигуры соперника. Все числа разделяются пробелом. Координаты всех клеток – натуральные числа, не превосходящие w та h соответственно. Сначала вводится вертикаль, потом горизонталь. Клетки, указанные как начальная и конечная, не содержат
фигур соперника; разные фигуры не могут находиться в одной и той же клетке. Программа должна вывести на экран единственное целое число — либо минимальное количество ходов, необходимых, чтобы дойти от указанной начальной клетки до указанной конечной, либо -1, если дойти невозможно
Примеры
Ввод
8 8 5 2 5 4 1 5 3
Вывод 2
Ввод
20 20 1 20 3 3 3 1 19 2 19 2 20
Вывод-1
|
