Технический форум
Вернуться   Технический форум > Программирование > Форум программистов > Помощь студентам


Ответ
 
Опции темы Опции просмотра
Старый 27.10.2011, 21:00   #1 (permalink)
Вива
Member
 
Регистрация: 22.10.2011
Сообщений: 14
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию Задача про стоки, Паскаль

Стоки
Карту местности условно разбили на квадраты, и посчитали среднюю высоту над уровнем моря для каждого квадрата.
Когда идет дождь, вода равномерно выпадает на все квадраты. Если один из четырех соседних с данным квадратом квадратов имеет меньшую высоту над уровнем моря, то вода с текущего квадрата стекает туда (и, если есть возможность, то дальше), если же все соседние квадраты имеют большую высоту, то вода скапливается в этом квадрате.
Разрешается в некоторых квадратах построить водостоки. Когда на каком-то квадрате строят водосток, то вся вода, которая раньше скапливалась в этом квадрате, будет утекать в водосток.
Если есть группа квадратов, имеющих одинаковую высоту и образующих связную область, то если хотя бы рядом с одним из этих квадратов есть квадрат, имеющий меньшую высоту, то вся вода утекает туда, если же такого квадрата нет, то вода стоит во всех этих квадратах. При этом достаточно построить водосток в любом из этих квадратов, и вся вода с них будет утекать в этот водосток.
Требуется определить, какое минимальное количество водостоков нужно построить, чтобы после дождя вся вода утекала в водостоки.
Формат входных данных
Во входном файле записаны сначала числа N и M, задающие размеры карты — натуральные числа, не превышающие 100. Далее идет N строк, по M чисел в каждой, задающих высоту квадратов карты над уровнем моря. Высота задается натуральным числом, не превышающим 10000. Считается, что квадраты, расположенные за пределами карты, имеют высоту 10001 (то есть вода никогда не утекает за пределы карты).
Формат выходных данных
В выходной файл выведите минимальное количество водостоков, которое необходимо построить.
Вива вне форума   Ответить с цитированием

Старый 27.10.2011, 21:00
Helpmaster
Member
 
Аватар для Helpmaster
 
Регистрация: 08.03.2016
Сообщений: 0

Возможно проблема уже решена в какой то из этих тем

Паскаль. Задача о сторожах
Паскаль. Задача об элементах вектора
Задача, Паскаль
Паскаль, задача

Старый 27.10.2011, 21:01   #2 (permalink)
Вива
Member
 
Регистрация: 22.10.2011
Сообщений: 14
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию

Примечание к задаче

Это задача на рекурсивный алгоритм. Хотя задача имеет большую вычислительную сложность, решение довольно компактное за счёт применения рекурсивной процедуры.

p – массив, высотой [n,m], по краям добавляем по ряду, поэтому [0..n+1, 0..m+1].
s – линейный массив 1+..n*m, если стока нет s=0, сток есть s=1.
а – массив меток, рассмотрели квадрат или нет. 0 – не смотрели, k – смотрели.
В рекурсивной процедуре onl просматриваем для каждой клетки наличие стоков во всех четырёх сторонах [x-1,y], [x+1,y], [x,y-1], [x,y+1]. Если уровень одинаков, то вызываем процедуру для соседней клетки.
Затем просматриваем массив s, считываем нули и выводим кол-во стоков
Вива вне форума   Ответить с цитированием
Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Выкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




Часовой пояс GMT +4, время: 11:49.

Powered by vBulletin® Version 6.2.5.
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.