Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 05.03.2019, 00:39   #1
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию Робинзон

Всем доброго времени суток. Прошу, как всегда помощи при решении задачи.
Задачка взята с сайта https://www.e-olymp.com/ru/problems/8703/
Собственно условие:
Наконец Робинзон скачал из Интернета фотографию своего острова и теперь может построить хижину на южном побережье. Остров Робинзона омывается со всех сторон океаном и имеет внутренние водоемы. Фотография — прямоугольная матрица размером N × M клеток, где 0 — клетка воды, 1 — клетка суши. Старая хижина Робинзона находится в клетке с координатами A, B. Помогите Робинзону выбрать клетку C, D на южном побережье для постройки новой хижины, так, чтобы время T перемещения между хижинами было минимальным. Если таких клеток несколько, достаточно указать одну из них. Движется Робинзон по соседним клетках через общие стороны и тратит: 1 час в клетке суши, и 3 часа в клетку с водой (время, затраченное на первую и последнюю клетки маршрута, тоже учитывается). Клетка южного побережья — последняя 1 в каждом столбце матрицы.
Прошу, чтобы подказали с чего начать. Спасибо
kim-im вне форума Ответить с цитированием
Старый 05.03.2019, 10:04   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
В первой строке числовые значения N, M, A, B — натуральные, не больше 100
матрицы не большие, поэтому можно попытаться решить задачу банальным перебором.
берём
Цитата:
Сообщение от kim-im Посмотреть сообщение
Клетка южного побережья — последняя 1 в каждом столбце матрицы.
в каждом столбце последнюю единицу и находим маршрут с минимальным временем от точки A,B до этой точки.

после цикла берём точку, где время было минимальным.

для поиска минимального пути из одной точки в другую наверняка есть разные алгоритмы.
Можно попробовать, например, использовать ДП (заполнить матрицу числами, начиная от конечной точки - числами, время прохода от конечной точки до данной). см. например, Двумерное динамическое программирование
Serge_Bliznykov вне форума Ответить с цитированием
Старый 05.03.2019, 15:41   #3
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение

для поиска минимального пути из одной точки в другую наверняка есть разные алгоритмы.
Скажите, а можно ли к этой задачи применить Алгоритм Флойда?
kim-im вне форума Ответить с цитированием
Старый 05.03.2019, 15:56   #4
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от kim-im Посмотреть сообщение
Скажите, а можно ли к этой задачи применить Алгоритм Флойда?
ну, я не знаю, как этот алгоритм можно применить в данном случае.
Но, наверное, если подумать, то можно и этот алгоритм использовать.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 05.03.2019, 16:00   #5
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
ну, я не знаю, как этот алгоритм можно применить в данном случае.
А что вы посоветуете? Для новичка в этих вопросах. В сети много разных способов. Не знаю за что взяться. Спасибо
kim-im вне форума Ответить с цитированием
Старый 05.03.2019, 16:08   #6
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

так я же кинул ссылку на описание решения аналогичной задачи через ДП.
на мой взгляд, это самый простой вариант. (просто не факт, что самый эффективный и быстрый).

пример.
берём точку 4 1 (это последняя единица в первом столбце) и заполняем матрицу расстояниями:
matrica_DP_41.png
запомнили, что минимальный путь из хижины в 4 1 занимает время 8 часов.

потом очищаем матрицу.
берём точку 4 2 (это последняя единица во втором столбце) и заполняем матрицу расстояниями.
получаем что минимальный путь из хижины в 4 1 занимает время 7 часов.

повторяем процедуру для всех столбцов.
берём минимальное из всех найденных значений.

куда уж проще то?

Последний раз редактировалось Serge_Bliznykov; 05.03.2019 в 16:26.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 07.03.2019, 10:40   #7
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
пример.
берём точку 4 1 (это последняя единица в первом столбце) и заполняем матрицу расстояниями:
запомнили, что минимальный путь из хижины в 4 1 занимает время 8 часов.
потом очищаем матрицу.
Спасибо за подказку. Только всё равно что-то не могу написать код. Не могли бы немного подсобить? Два дня читаю, учу, смотрю коды, но увы?
Только начало:
Код:
var i,j,n,m,a,b,c,d,t: integer;
    mas: array[1..100,1..100] of integer;
    
begin
 read (n,m,a,b);
 for i:=1 to n do
  begin
  for j:=1 to m do
   begin
    read (mas[i,j]);
   end;
  end;
   read (a,b);
   
 end.
kim-im вне форума Ответить с цитированием
Старый 07.03.2019, 11:57   #8
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию

Доработал как заполнить последний ряд числами при условии.
Код:
var i,j,n,m,a,b,c,d,t: integer;
    mas: array[1..100,1..100] of integer;
    
begin
 read (n,m);
 for i:=1 to n do
  begin
  for j:=1 to m do
   begin
    read (mas[i,j]);
   end;
  end;
   
   for j:=1 to m do 
      begin
       if mas[n,j]=0 then mas[n,j]:=1 else mas[n,j]:=3;
        write (mas[n,j],' ');
      end;
 end.
kim-im вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск