e-olymp 1060. Линии

Задача взята с сайта e-olymp.com.

Условие задачи

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

Входные данные

В первой строке находится число [latex]n \left (2\leq n\leq 40 \right )[/latex], в каждой из следующих [latex]n[/latex] строк — по [latex]n[/latex] символов. Символом точки обозначена свободная клетка, латинской заглавной [latex]O[/latex] — шарик, [latex]@[/latex] — исходное положение шарика, который должен двигаться, латинской заглавной [latex]X[/latex] — конечное положение шарика.

Выходные данные

В первой строке выводится [latex]Y[/latex], если движение возможно, или [latex]N[/latex], если нет. Если движение возможно далее следует [latex]n[/latex] строк по [latex]n[/latex] символов — как и на вводе, но [latex]X[/latex], а также все точки на пути заменяются плюсами.

Тесты

Входные данные Выходные данные

Код программы

ideone.com

Засчитанное решение на e-olymp.com.

Решение

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

Затем, если клетка с конечным положением шарика достижима, необходимо восстановить кратчайший путь. Двигаясь от конечной позиции в начальную, на каждом шаге выбираем клетку значение которой на единицу меньше текущего положения, при этом символы в соответствующих клетках исходного лабиринта заменяем на символ [latex]+.[/latex]

e-olymp 4850. Шайтан-машинка

Марченко Філіп Олександрович
Марченко Філіп Олександрович

Latest posts by Марченко Філіп Олександрович (see all)

Шайтан-машинка

Условие

У Ибрагима есть магическая чёрная шайтан-машинка. На ней есть три кнопки и табло. Табло может показывать не более чем четырёхзначные числа. Каждая из кнопок меняет число некоторым образом: первая домножает его на [latex]3[/latex], вторая прибавляет к нему сумму его цифр, а третья вычитает из него [latex]2[/latex]. В случае, если число становится отрицательным или превосходит [latex]9999[/latex], шайтан-машинка ломается.

Ибрагим может нажимать кнопки в любом порядке. Его интересует, как ему получить на табло число [latex]b[/latex] после некоторой последовательности нажатий, если сейчас шайтан-машинка показывает [latex]a[/latex]. Помогите ему найти минимальное необходимое число нажатий.

Входные данные

В одной строке находится два натуральных числа [latex]a[/latex] и [latex]b[/latex] [latex](1\leq{a},b\leq9999)[/latex].

Выходные данные

Вывести минимальное необходимое количество действий.

Задача
Зачтённое решение

Код

Ideone

Код на Java:

 

Решение

Для решения данной задачи я решил использовать алгоритм BFS (поиск в ширину). Обычно, данный алгоритм применяется для поиска пути от одной вершины к другой, причём длина пути должна быть минимальной.

Всю «карту» расположения операций можно представить в виде графа-дерева, где от каждой вершины отходят максимум 3 ребра (в каждой вершине по операции, проделанной со значением вершины, которая находится на уровень выше). Будем рассматривать каждую вершину. Если исходная вершина и есть конечной, то выходим из программы с вердиктом «0». Иначе будем поочерёдно рассматривать все вершины. Заведём массив расстояний, в котором предположим, что расстояние до нужной нам вершины равно 1. С проходом каждой вершины будем подсчитывать расстояние до нужной нам вершины (прибавляя к расстоянию 1), в которую мы рано или поздно попадём.

e-olymp 432. Подземелье

Царев Николай Александрович
Царев Николай Александрович

Latest posts by Царев Николай Александрович (see all)

Подземелье

   Вы попали в 3D подземный лабиринт и необходимо найти быстрый выход! Карта подземелья составлена из единичных кубических комнат, по которым можно или нельзя передвигаться. Нужно всего одну минуту, чтобы переместиться она одну единицу на север, юг, восток, запад, вверх или вниз. Вы не можете двигаться по диагонали, и лабиринт окружен твердой скальной породой со всех сторон.

   Можно ли выбраться из лабиринта? Если да, то какое времени это займет?

Техническое условие

   Входные данные

Состоит из ряда подземелий. Каждое описание подземелья начинается со строки, содержащей три целых числа: количество уровней в подземелье l, а также r и cколичество строк и столбцов, описывающих план каждого уровня (все числа не больше 30).

   Далее следует l блоков по r строк, каждая по c символов. Каждое число описывает одну ячейку подземелья. Запрещенные для перемещения кубы подземелья обозначены символом ‘#‘, а пустые клетки обозначены ‘.‘. Ваша стартовая позиция обозначается буквой ‘S‘, а выход буквой ‘Е‘. Все описания подземелий отделены пустой строкой. Описание входных данных заканчивается тремя нулями.

   Выходные данные

   Для каждого лабиринта необходимо вывести одну строку. Если есть возможность добраться до выхода, вывести строку вида

Escaped in X minute(s).

    где X — наименьшее время, необходимое для достижения выхода.

   Если достичь выход невозможно, вывести строку

   Trapped!


 

ТЕСТЫ:

Входные данные

Выходные данные

 

Тесты взяты с сайта e-olimp. Подтверждение прохождения задачи на e-olimp.

Задача (Подземелья)

 

Задача на E-Olimp!

ССЫЛКА НА IDEONE.COM

(Программа также проверенна в Code::Blocks)


Алгоритм решения:

Основа всего алгоритма — поиск в ширину, реализованный на трехмерном массиве.  Для реализации я использовал собственную структуру очереди. В двух словах идея такова:
1) Считываем данные, заполняя массив по принципу:  Если «комната закрыта» — ставим -1. Если открыта — ставим ноль. Старт и Финиш также заполняем нулями, но запоминаем их координаты.
Также создаем массив булевых переменных, помогающий нам определять, посещали ли мы уже эту вершину. Этот массив вначале заполняется нулями.
2) Реализация самого поиска. Создаем очередь и помещаем в нее стартовую вершину.  Затем запускаем цикл до тех пор, пока очередь не пуста.
3) Действия в цикле повторяются шесть раз, на каждое из возможных направлений.
  • Проверяем закрыта ли эта комната ( проверка на положительное число)
  • Если комната открыта, проверяем, есть ли в ней уже какое то время. Если да, то кладем в нее минимум из времени пути который был уже проложен, и проложен сейчас. В противном случае, кладем в нее время данного пути.
  • Проверяем, была ли посещена эта комната ранее. В противном случае — отмечаем что она посещалась и добавляем ее в очередь.

4) Извлекаем вершину из очереди.

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

Примечание! 

1)Для удобной реализации поиска, оба массива создаем на два уровня больше, как бы делая ему рамку ( маску).

2) Поскольку в одном тесте идет не один набор уровней, программа выполняется в цикле, который работает до тех пор, пока не получит в качестве трех чисел — три нуля. ( В комментариях назовем этот цикл «внешним»)


 

 

e-olymp 1061. Покраска лабиринта

Сорокина Полина
Сорокина Полина

Latest posts by Сорокина Полина (see all)

Задача e-olimp 1061.

Лабиринт представляет собой квадрат, состоящий из N×N сегментов. Каждый из сегментов может быть либо пустым, либо заполненным камнем. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесен снизу, сверху, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри.  Помогите ему рассчитать количество краски, необходимой для этого.

Входные данные

В первой строке находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решетка — сегмент со стеной.

3N33, размер сегмента 3×3, высота стен 3 метра.

Выходные данные

Вывести одно число — площадь видимой части внутренних стен лабиринта в квадратных метрах.

Пример

Входные данные Выходные данные
5

. . . . .

. . . # #

. . # . .

. . # # #

. . . . .

198

C++:

Java:

Для решения задачи я использовала алгоритм поиска в ширину: начиная с левой верхней клетки, которая гарантированно пуста, проверяю все смежные с ней и заношу их в план проверки. Для каждой клетки считаю количество пустых смежных клеток и получаю число стен рядом с ней. Чтобы было удобно проверять смежные клетки на пустоту, я сделала «стену» вокруг данного лабиринта. После проверки клетки отмечаю, что она просмотрена.

Так как в условии не гарантируется, что есть проход от левой верхней до правой нижней клетки, проверяю, посещена ли последняя. Если нет, снова запускаю поиск, начиная с неё.

Засчитанное решение.

Задача на Ideone:
C++
Java