Средние Очередь. Поиск пути 27.02.2016

1. Лабиринт - 1

Есть лабиринт. Он представляет собой прямоугольник N (строк) на M (столбцов). Мальчик находится в клетке с координатами (X0; Y0). Сможет ли он пробраться в клетку
(X1; Y1), если мальчик может двигаться по горизонтали или по вертикали.

Начало координат, клетка (1; 1), находится в первой строке и в первом столбце.

Ограничения: 1< = N, M < = 100 1< = X0, X1 < = N 1< = Y0, Y1 < = M

Примечание: Мальчик всегда появляется на свободной клетке.

В лабиринте: 1 - стена. 0 - проход.

Формат ввода: N M - размер лабиринта.

X0, Y0 - координаты начального положения мальчика.

X1, Y1 - координаты клетки, в которую мальчику необходимо попасть.

Далее следует N строк - описание лабиринта.

Формат вывода: Yes/No - 'Yes' в случае когда мальчик сможет добраться до нужной клетки и 'No' в противном случае. Если 'Yes', то вывести путь.

2. 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 < = М, P < = 10⁵).

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

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

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

Program Ochered_poisk_puti;

var

a: array[0..101, 0..101] of integer;

b: array[1..2, 1..10000] of byte;

i, j, shag, n, m: integer;

x0, y0, x1, y1, x, y: integer;

t, no, ko, sv, temp,: longint;

c: array[1..2, 1..1000] of byte;

ch: byte;

Begin

assign (input, 'input.txt');

assign (output, 'output.txt');

reset (input);

rewrite (output);

{ читаемисходныеданные }

readln(n, m);

readln (x0, y0);

readln (x1, y1);

for i: =0 to n+1 do

for j: =0 to m+1 do

a[i, j]: =-1;

for i: =1 to n do

for j: =1 to m do

begin

read(ch);

ifch=0 then a[i, j]: =0;

end;

{ если финиш в точке старта – ставим «заглушку» }

if (x0=x1) and (y0=y1) then

begin

writeln('Yes');

writeln(x0, ' ', y0);

close (input);

close (output);

halt;

end;

{ задаем начальные значения }

a[x0, y0]: =-2;

b[1, 1]: =x0;

b[2, 1]: =y0;

no: =1; ko: =1; sv: =2; shag: =1;

{ запускаемочередь}

while true do

begin

temp: =sv;

for i: =no to ko do

begin

x: =b[1, i];

y: =b[2, i];

{ шагвверх }