|
Читайте также: |
Всероссийская олимпиада школьников. Муниципальный этап
Предмет: программирование
Класс: 9-11
Вводная часть
Каждому участнику муниципального этапа предлагается для решения пять задач. Решением задачи является исходный текст программы.
Жюри рассматривает только консольные приложения на языках программирования Паскаль, С/С++, Basic, Java. В комментариях следует указать компилятор, использованный участником.
Программа должна обязательно вводить исходные данные из текстового файла input. и выводить результат в текстовый файл output.txt.
Файлы с исходными текстами программ необходимо называть в точности так, как указано в условии. Например, если участник пишет на языке С++, то файл с решением задачи A он должен назвать lab.cpp (если программа написана на другом языке, то расширение будет другим). Жюри не рассматривает неправильно названные файлы. Кроме того, участник не должен сдавать несколько вариантов решения одной и той же задачи. В этом случае жюри может не рассматривать ни один из вариантов.
Для каждой задачи жюри имеет по 20 тестов. Тесты, приведённые в условии задачи, могут входить или не входить в состав тестов жюри. Количество баллов, набранных участником, в точности равно количеству тестов, пройденных его программой. Тест считается пройденным, если программа вывела верный результат и работала не более 1 секунды. Для программ, написанных на языке Basic и откомпилированных в среде QBasic4.5, жюри может увеличить лимит времени. Таким образом, участник муниципального этапа может набрать в сумме 100 баллов.
После окончания олимпиады вы можете принять участие в обсуждении задач на форуме olymp.baltinform.ru/forum à «Информатика и ИКТ» à «Муниципальный этап Всероссийской олимпиады».
Всероссийская олимпиада школьников. Муниципальный этап
Классы
Задача A. «Лабиринт»
Имя файла с исходным текстом программы: lab
Входной файл: input.txt
Выходной файл: output.txt
Ограничение по времени: 1 секунда
Ограничение по памяти: 64M байт
Максимальная оценка: 20 баллов
Анна и Борис попали в лабиринт. Лабиринт представляет собой двумерную прямоугольную таблицу, поделённую на N × M одинаковых квадратов. Квадраты либо пусты, либо заняты стенами. Из пустого квадрата можно переходить в любой из четырёх соседних квадратов, если они пусты. На это требуется одна единица времени. А можно оставаться на прежнем месте.
Напишите программу, вычисляющую наименьшее время, через которое Анна и Борис могут встретиться в одном квадрате лабиринта.
Вход
В первой строке входного файла записаны натуральные числа N и M (4 ≤ N, M ≤ 500). В остальных N строках файла записано по M символов в каждой. Символ ‘ # ’ (ASCII 35) обозначает квадрат, занятый стеной, символ ‘. ’ (ASCII 46) – пустой квадрат, символ ‘ A ’ (ASCII 65) – квадрат, в котором находится Анна, и символ ‘ B ’ (ASCII 66) – квадрат, в котором находится Борис. Лабиринт со всех сторон окружён стенами, выход из него невозможен.
Выход
Запишите в выходной файл минимальное время, которое потребуется Анне и Борису, чтобы встретиться в одном квадрате. Если это невозможно, запишите в выходной файл число -1 (минус единица).
Примеры входа и выхода
| input.txt | output.txt |
| 5 7 ####### #.A...# #####.# #..B..# ####### |
Дата добавления: 2015-07-08; просмотров: 414 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Задание №1 | | | Подзадачи |