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

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


 

Герои

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

Коварный кардинал Ришелье вновь организовал похищение подвесок королевы Анны; вновь спасать королеву приходится героическим мушкетерам. Атос, Портос, Арамис и д’Артаньян уже перехватили агентов кардинала и вернули украденное; осталось лишь передать подвески королеве Анне. Королева ждет мушкетеров в дворцовом саду. Дворцовый сад имеет форму прямоугольника и разбит на участки, представляющие собой небольшие садики, содержащие коллекции растений из разных климатических зон. К сожалению, на некоторых участках, в том числе на всех участках, расположенных на границах сада, уже притаились в засаде гвардейцы кардинала; на бой с ними времени у мушкетеров нет. Мушкетерам удалось добыть карту сада с отмеченными местами засад; теперь им предстоит выбрать наиболее оптимальные пути к королеве. Для надежности друзья разделили между собой спасенные подвески и проникли в сад поодиночке, поэтому начинают свой путь к королеве с разных участков сада. Двигаются герои по максимально короткой возможной траектории.

Марлезонский балет вот-вот начнется; королева не в состоянии ждать героев больше L минут; ровно в начале L+1-ой минуты королева покинет парк, и те мушкетеры, что не успеют к этому времени до нее добраться, не смогут передать ей подвески. На преодоление одного участка у мушкетеров уйдет ровно по минуте. С каждого участка мушкетеры могут перейти на 4 соседние. Требуется выяснить, сколько подвесок будет красоваться на платье королевы, когда она придет на бал.

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

Первая строка входного файла INPUT.TXT содержит целые числа N и M (1 ≤ N,M ≤ 20) – размеры сада. Далее идут N строк по M символов в каждом; символы '0' соответствуют участкам, на которых нет засады, символы '1' – участкам, на которых разместились гвардейцы. В N+2-ой строке теста записано три целых числа: координаты участка, на котором королева будет ждать мушкетёров (Qx, Qy) (1 < Qx < N, 1 < Qy < M) и время в минутах до начала балета (1 ≤ L ≤ 1000). В N+3-ей строки записаны через пробел целые числа координаты участка, с которого стартует Атос (Ax,Ay) (1 < Ax < N, 1 < Ay < M) и количество подвесок, хранящихся у него (1 ≤ Pa ≤ 1000). В N+4, N+5 и N+6-ой строках аналогично записаны стартовые координаты и количество подвесок у Портоса, Арамиса и д’Артаньяна.

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

В выходной файл OUTPUT.TXT выведите количество подвесок, которое королева успеет получить у мушкетеров до начала балета.

Примеры

INPUT.TXTOUTPUT.TXT
15 5
11111
10001
10001
10001
11111
4 4 10
2 2 1
2 3 2
3 2 3
3 3 4
10
25 5
11111
10001
10111
10101
11111
4 4 10
2 2 1
2 2 2
2 2 3
2 2 4
0

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


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Базовые понятия
 Представление графа
 Поиск в глубину
 Поиск в ширину
 A. Путь
 B. Один конь
 C. Табличка
 D. Грядки
 E. Звезда
 F. Морской бой - 3
 G. Два коня
 H. Лабиринт с тигром
 I. Алхимия
 J. Игра - 4
 K. Игра Jammed
 L. Числа
 M. Кладоискатель
 N. Водолей
 O. Lines - 2
 P. Ладья в лабиринте
 Q. Игрушечный лабиринт
 R. Лабиринт
 S. Мосты
 T. Цивилизация
 U. Только направо
 V. Герои
 W. Лабиринт минотавра
 X. Наименьшее кратное
 Y. Космические исследования
 Z. Кубик Рубика

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



Про автомобили