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', то вывести путь.
| Пример ввода: 3 3 1 1 3 3 0 0 0 0 1 0 1 1 0 | Пример вывода: Yes 1 1 1 2 1 3 2 3 3 3 |
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 <= 105).
Далее в N строках задается карта местности, в каждой из которых по М символов: символ ‘+’ - доступные для передвижения квадраты, символ ‘-’ недоступные квадраты и символ ‘#’ - телепорты.
Во N+2 строке – число К (0 <= К <= 8) – количество телепортов. В следующий К строках по четыре числа in1, in2, out1, out2, описывающие точкивхода (in1, in2) и выхода (out1, out2) каждого телепорта, (1 <= in1, out1 <= N, 1 <= in2, out2 <= М)
Выходные данные: В выходной файл output.txt необходимо вывести наименьшее количество единиц потраченной роботом энергии или фразу ‘No way’, если попасть из квадрата А в квадрат В невозможно.
4. Листок
Из листа клетчатой бумаги размером МхN удалили некоторые клетки размером 1х1. Определить, на сколько кусков распадается оставшаяся часть листа. Две клетки не распадаются, если они имеют общую сторону.
Ввод из файла list.in. В первой строке находятся два числа М и N (1 ≤ N, М ≤ 100), в следующих М строках – по N символов. Если клетка не вырезана, этому соответствует знак #, если вырезана – точка.
Вывод в файл list.out. Единственное число – количество кусков, на которые распадается лист.
Пример
| № | input.txt | output.txt |
| 4 8 #.##.#.# ......## #.###.## ##.##.## |
5. Химическая тревога
(Время: 1 сек. Память: 16 Мб Сложность: 50%)
Произошло радиоактивное заражение местности. Составлена карта зараженности. Она представляет собой прямоугольную таблицу N*M, в клетках которой записана зараженность соответствующего участка.
Требуется написать программу, которая найдет путь из левой верхней клетки таблицы в правую нижнюю клетку с минимальной суммарной дозой радиации.
Входные данные
Входной файл INPUT.TXT содержит в первой строке числа N и M, а в следующих N строках – по M чисел – карта зараженности местности. Числа в строках разделяются одним пробелом. 1<=N<=30, 1<=M<=30, зараженность участка – целое число от 0 до 100.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно число – суммарную долю радиации.
Пример
| № | input.txt | output.txt |
| 3 5 2 100 0 100 100 1 100 0 0 0 1 0 3 100 2 |