|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
05.03.2019, 00:39 | #1 |
Пользователь
Регистрация: 07.11.2017
Сообщений: 42
|
Робинзон
Всем доброго времени суток. Прошу, как всегда помощи при решении задачи.
Задачка взята с сайта https://www.e-olymp.com/ru/problems/8703/ Собственно условие: Наконец Робинзон скачал из Интернета фотографию своего острова и теперь может построить хижину на южном побережье. Остров Робинзона омывается со всех сторон океаном и имеет внутренние водоемы. Фотография — прямоугольная матрица размером N × M клеток, где 0 — клетка воды, 1 — клетка суши. Старая хижина Робинзона находится в клетке с координатами A, B. Помогите Робинзону выбрать клетку C, D на южном побережье для постройки новой хижины, так, чтобы время T перемещения между хижинами было минимальным. Если таких клеток несколько, достаточно указать одну из них. Движется Робинзон по соседним клетках через общие стороны и тратит: 1 час в клетке суши, и 3 часа в клетку с водой (время, затраченное на первую и последнюю клетки маршрута, тоже учитывается). Клетка южного побережья — последняя 1 в каждом столбце матрицы. Прошу, чтобы подказали с чего начать. Спасибо |
05.03.2019, 10:04 | #2 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
берём в каждом столбце последнюю единицу и находим маршрут с минимальным временем от точки A,B до этой точки. после цикла берём точку, где время было минимальным. для поиска минимального пути из одной точки в другую наверняка есть разные алгоритмы. Можно попробовать, например, использовать ДП (заполнить матрицу числами, начиная от конечной точки - числами, время прохода от конечной точки до данной). см. например, Двумерное динамическое программирование |
|
05.03.2019, 15:41 | #3 |
Пользователь
Регистрация: 07.11.2017
Сообщений: 42
|
|
05.03.2019, 15:56 | #4 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
|
05.03.2019, 16:00 | #5 |
Пользователь
Регистрация: 07.11.2017
Сообщений: 42
|
|
05.03.2019, 16:08 | #6 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
так я же кинул ссылку на описание решения аналогичной задачи через ДП.
на мой взгляд, это самый простой вариант. (просто не факт, что самый эффективный и быстрый). пример. берём точку 4 1 (это последняя единица в первом столбце) и заполняем матрицу расстояниями: matrica_DP_41.png запомнили, что минимальный путь из хижины в 4 1 занимает время 8 часов. потом очищаем матрицу. берём точку 4 2 (это последняя единица во втором столбце) и заполняем матрицу расстояниями. получаем что минимальный путь из хижины в 4 1 занимает время 7 часов. повторяем процедуру для всех столбцов. берём минимальное из всех найденных значений. куда уж проще то? Последний раз редактировалось Serge_Bliznykov; 05.03.2019 в 16:26. |
07.03.2019, 10:40 | #7 | |
Пользователь
Регистрация: 07.11.2017
Сообщений: 42
|
Цитата:
Только начало: Код:
|
|
07.03.2019, 11:57 | #8 |
Пользователь
Регистрация: 07.11.2017
Сообщений: 42
|
Доработал как заполнить последний ряд числами при условии.
Код:
|