Огонь и лёд
(Время: 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.TXT | OUTPUT.TXT |
1 | 3 3 5
FAI
IFI
FBF
2 0 3
1 5 3
4 0 5 | 2 5 |
2 | 3 3 1
AFI
FXI
IIB
0 9 9
9 0 9
9 9 0 | impossible impossible |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|