Средние Очередь. Решение задач 27.02.2016

1. Один конь

На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?

Входные данные: Входной файл input.txt содержит пять чисел: N, x1, y1, x2, y2 (5 < = N < = 20, 1 < = x1, y1, x2, y2 < = N). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).

Выходные данные: В выходной файл output.txt необходимо вывести наименьшее число ходов коня.

2. Два коня

На стандартной шахматной доске (8х8) живут 2 шахматных коня: красный и зеленый. Обычно они беззаботно скачут по просторам доски, пощипывая шахматную травку, но сегодня особенный день: у зеленого коня день рождения. Зеленый конь решил отпраздновать это событие вместе с красным. Но для осуществления этого прекрасного плана им нужно оказаться на одной клетке. Заметим, что красный и зеленый шахматные кони сильно отличаются от черного с белым: они ходят не по очереди, а одновременно, и если оказываются на одной клетке, никто никого не съедает. Сколько ходов им потребуется, чтобы насладиться праздником?

Входные данные: Во входном файле input.txt содержатся координаты коней, записанные по стандартным шахматным правилам (т.е. двумя символами - маленькая латинская буква (от a до h) и цифра (от 1 до 8), задающие столбец и строку соответственно).

Выходные данные: Выходной файл output.txt должен содержать наименьшее необходимое количество ходов, либо -1, если кони не могут встретиться.

3. Lines

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

Входные данные: В первой строке входного файла input.txt находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика. (2 < = N < = 50)

Выходные данные: В выходной файл output.txt выведите в первой строке Yes, если движение возможно, или No, если нет. Если движение возможно, то далее следует вывести N строк по N символов - как и на вводе, но букву X, а также все точки по пути следует заменить плюсами. Если решений несколько, выведите любое.

3. Робот-космонавт

Свершилось! Земляне колонизировали планету Альфа звездной системы Тау Кита. Но вот незадача – жить там и добывать суперполезные ископаемые в условиях азотно-кислотной атмосфере могут пока только роботы-космонавты, энергия которых небезгранична. Поэтому любое движение робота должно быть как можно экономнее: желательно попасть из точки А в точку В за минимальное количество шагов. Робот может двигаться только в четырех направлениях: вперед, назад, влево и вправо (ландшафты планеты это позволяют). Но на Альфе есть необычная аномалия: червоточины пространственного континуума (или коротко – телепорты). Робот может шагнуть в квадрат с телепортом как в обычный свободный квадрат, а следующим шагом или шагнуть в соседний свободный квадрат или воспользоваться телепортом. Роботы-испытатели за несколько лет колонизации успели исследовать все телепорты и выяснить не только их координаты (in1, in2), но и координаты точек, в которые из них можно попасть (out1, out2).

У Вас имеется расчерченная на квадраты самая свежая карта участка местности размером N х M, на котором отмечены все доступные для передвижения квадраты (символ ‘+’), недоступные квадраты (символ ‘-’) и телепорты (символ ‘#’), а также отдельно – список координат телепортов и клеток, в которые они ведут (телепорты односторонние).

На перемещение из одного квадрата в любой соседний, а также на прыжок через телепорт робот тратит Р единиц энергии. Вам предстоит выяснить минимальное количество единиц энергии робота-космонавта, которое он потратит, чтобы добраться из квадрата А (x1, y1) в квадрат В (x2, y2).

Входные данные: В первой строке входного файла input.txt содержится семь целых чисел:
N, М, Р, x1, y1, x2, y2 (5 < = N, М < = 30, 1 < = x1, x2 < = N, 1 < = y1, y2 < = М).

Далее в N строках задается карта местности, в каждой из которых по М символов: символ ‘+’ - доступные для передвижения квадраты, символ ‘-’недоступные квадраты и символ ‘#’ - телепорты.

Во N+2 строке – число К (0 < = К < = 8)– количество телепортов. В следующий К строках по четыре числа in1, in2, out1, out2, описывающие точкивхода (in1, in2) и выхода (out1, out2) каждого телепорта, (1 < = in1, out1 < = N, 1 < = in2, out2 < = М)

Выходные данные: В выходной файл output.txt необходимо вывести наименьшее количество единиц потраченной роботом энергии или фразу ‘Noway’, если попасть из квадрата А в квадрат В невозможно.

Доделать тесты!!!