Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Огонь и лёд

(Время: 5 сек. Память: 16 Мб Сложность: 53%)

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

На поле есть ровно одна стартовая клетка и ровно одна целевая (конечная) клетка. Остальные клетки имеют один из трёх типов:

F – клетка охвачена пламенем;

I – клетка покрыта холодом;

X – стена, непроходимая клетка.

Перед стартом игры герою необходимо выбрать стихию, которую он будет представлять – огонь или лёд. Клетки, покрытые пламенем и холодом, обладают своей силой. После каждого хода герой получает урон, если клетка противоположной стихии, или лечение, если клетка своей стихии. Урон и лечение соответствуют силе клетки, в которой герой находится.

В начале игры здоровье героя равно H и не может превысить это значение во время игры. Если здоровье героя опустится ниже единицы, то игра закончится.

Определите минимальное количество ходов, необходимое, чтобы добраться из стартовой клетки в конечную для обеих стихий, выбранных на старте.

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

Первая строка входного файла INPUT.TXT содержит целые числа N, M и H – размеры поля и максимальное здоровье героя соответственно (1 ≤ N, M, H ≤ 100).

Следующие N строк содержат по M символов в каждой – описание карты. Символ F обозначает клетку с огнём, I – клетку со льдом, X – стену, A и B – стартовая и конечная клетки соответственно.

Следующие N строк содержат по M целых чисел – силы соответствующих клеток. Гарантируется, что силы стартовой и конечной клеток равны нулю. Остальные силы являются целыми числами от 1 до 100.

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

В первой строке выходного файла OUTPUT.TXT выведите ответ для стихии огня, во второй – для стихии льда. В тех случаях, когда герой не может добраться до конечной клетки, следует вывести «impossible» (без кавычек).

Примеры

INPUT.TXTOUTPUT.TXT
13 3 5
FAI
IFI
FBF
2 0 3
1 5 3
4 0 5
2
5
23 3 1
AFI
FXI
IIB
0 9 9
9 0 9
9 9 0
impossible
impossible

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 2023 / 2024
 2024 / 2025
 A. Горсть монет
 B. Количество байт
 C. Вложенные рамки
 D. Муравей
 E. День рождения
 F. Огонь и лёд
 G. Скучные запросы
 H. Мотивация
 I. Сыграешь с Денисом?
 J. Космический мусор

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru