![]() |
|
Модераторы: Poseidon |
![]()
|
|
| WWWeb |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 42 Регистрация: 10.7.2005 Репутация: нет Всего: нет |
На доске размером NxM ведется игра. В каждой клеточке поля либо стена либо
штраф, заданный некоторым числом. Вам надо дойти из клетки (xn,yn) в клетку (xk,yk). Можно ходить только в смежные клетки, то есть клетки, имеющие общую сторону. Нельзя заходить в клетку со стеной. Вам нужно найти путь из начальной клетки в конечную по вышеуказанным правилам так, чтобы суммарный штраф, собранный по пути, был минимален. Примечание 1: штраф начальной клетки входит в суммарный штраф, суммарный штраф<=50000. Примечание 2: стена обозначается как -1. Входные данные: N M - размеры xn yx - координаты начальной клетки xk yk - координаты конечной клетки a[1,1] a[1,2] ... a[1,m] a[2,1] a[2,2] ... a[2,m] - поле ... a[n,1] a[n,2] ... a[n,m] Выходные данные: Yes st -если можно дойти (st - минимальный штраф). No - если дойти нельзя. Ограничения: 0<n<51 0<m<51 0<xn,xk<=n 0<yn,yk<=m -2<a[i,j] Пример ввода: 3 3 1 1 3 3 1 1 1 1 -1 -1 2 2 2 Пример вывода: Yes 8 |
|||
|
||||
| Mayk |
|
|||
![]() ^аВаТаР^ сообщение>> ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 2616 Регистрация: 22.5.2005 Где: за границей разум а Репутация: 5 Всего: 134 |
Юзай волновой алгоритм.
-------------------- Здесь был кролик. Но его убили. Человеки < кроликов, йа считаю. |
|||
|
||||
![]()
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |