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

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

HotLog


 

Герои

(Время: 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)2006 - 2019, E-mail: admin@acmp.ru