15
Внимание!!! Следующая задача, наверное, наиболее сложная из всех задач, написанных мною. Я
до сих пор не уверен - есть ли у нее общее решение.
Читатель, наверно, уже определил явную любовь автора к задачам, связанным с лабиринтом. Бо-
лее того, идет молва, что если он (автор) в жюри - жди задачи на лабиринт.
Идея задачи “Подземелье Джафара” была предложена членом сборной команды Казахстана -
учеником 10 класса Берлизевым А (сш 28 г.Алматы), во время олимпиады ICI-94,
ПОДЗЕМЕЛЬЕ ДЖАФАРА
Первенство г. Алматы, 1995г., I-тур автор Даулеткулов А.
Каждую ночь Они стоят перед моими глазами... Мои друзья, не вернувшиеся из этого проклято-
го подземелья...
После отчаянной схватки, мы уничтожили охрану Джафара, но он успел скрыться в своем под-
земелье. Преследуя его, мы, не задумываясь, бросились за ним. Подземелье представляло собой гро-
мадный лабиринт. Мы бежали по его бесконечным запутанным переходам, пытаясь отыскать
Джафара. Через некоторое время мы остались вдвоем с Али, остальные мои друзья затерялись
где-то в лабиринте...
Тут раздался зловещий смех Джафара, заманившего нас в ловушку. Пол под нами начал провали-
ваться. Мы побежали с Али, не останавливаясь...
Каждую ночь Они стоят перед моими глазами... Мои друзья, не вернувшиеся из этого проклято-
го подземелья...
План лабиринта и исходное положение Ваших друзей находятся во входном файле “TESTx.TXT”
(х - номер варианта теста).
Блок информации входного файла начинается с данных о размерах лабиринта: первое число -
количество строк, второе - количество столбцов (Пример 1). Затем следует кодовая информация о ла-
биринте. Код для каждой отдельной горизонтали является отдельной строкой файла и представляет
собой последовательность цифр 1 и 0 (1 - стена лабиринта, 0 - свободное пространство). После ин-
формации о плане лабиринта следует информация о количестве (L) и о положении Ваших друзей в
лабиринте (первое число - номер строки, второе - номер столбца).
ПОСТАНОВКА ЗАДАЧИ
Написать программу, которая выполняет следующие действия:
1. Вводит с клавиатуры имя входного файла.
2. Считывает из входного файла план лабиринта, отображает его на экране дисплея в виде пря-
моугольной матрицы NxM (N - количество строк, M - количество столбцов). При этом символ звез-
дочка ( * ) обозначает стены лабиринта, символ пробел ( ) - свободное пространство, символ ( x ) -
исходные положения Ваших друзей.
3. Определяет возможность выхода всех друзей из лабиринта.
4. Отображает кратчайшие пути выхода их из лабиринта (числами от 1 до L i , где 1 - первый
ход).
5. В случае невозможности выхода хотя бы одного из друзей, выдает сообщение: “Я проиграл”.
ТЕХНИЧЕСКИЕ ОГРАНИЧЕНИЯ
1. 3 < N < 20 , 5 < M < 40 , 2 < L < 10 .
2. За один ход необходимо продвинуться на одно свободное поле вверх-вниз, направо или налево
(двигаться по диагонали или стоять на месте нельзя).
3. Поле, пройденное хотя бы одним человеком, становится непроходимым.
4. Имя входного ASCII файла должно быть “TESTx.TXT” , где х - номер варианта.
Пример 1.