Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
ivy
0 / 0 / 0
Регистрация: 22.12.2013
Сообщений: 8
#1

Выбирать поле таким образом, чтобы необходимая площадь для разворота суммарно была минимальной - C++

22.12.2013, 18:30. Просмотров 297. Ответов 0
Метки нет (Все метки)

прошу помощи в решении задачи
сабж:
Кликните здесь для просмотра всего текста
Пусть имеется прямоугольное поле размерами n x m участков. Каждый из участков либо доступен для посадки моркови, либо нет. Поскольку обработка участка ведется с помощью трактора, необходимо выбрать прямоугольный участок поля, который будет засеваться морковью в параллельные грядки. Этот прямоугольник должен иметь максимальную площадь и состоять только из доступных участков. Площадь, требуемая трактору для перехода с одной грядки на следующую соответствует одному доступному участку в конце каждой грядки. Нужно выбирать поле таким образом, чтобы необходимая площадь для разворота суммарно была минимальной.
Нужный прямоугольник может иметь стороны, не параллельные сторонам исходного поля.


комментарии: на одном участке - одна грядка. использовать недоступные участки для разворота нельзя. вывести нужно номера участков, которые хотя бы частично принадлежат прямоугольнику. искать нужно максимальный прямоугольник, а потом из всех прямоугольников с такой площадью выбрать тот, у которого площадь разворота наименьшая.

----|
|---|
|---|
----|

тут - грядка, | место разворота, начинает с левого верхнего угла

Вот мне интересно, это вообще реализуемо? нахождение прямоугольника, который наложили на матрицу 0 и 1 только на нули допустим, и при этом наибольшей площади? А если считерить и считать за площадь кол-во клеток, принадлежащих прямоугольнику?
Прямоугольник, параллельный осям, нашел, а вот к наклонному не могу подступиться

язык с++, но мне бы идею хотя бы

задача к зачету, зачет во вторник(

Добавлено через 12 часов 7 минут
up up

Добавлено через 4 часа 26 минут
up....
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.12.2013, 18:30     Выбирать поле таким образом, чтобы необходимая площадь для разворота суммарно была минимальной
Посмотрите здесь:

В матрице M x N переставить строки таким образом, чтобы... C++
Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. C++
Дан вещественный массив А (n). Отсортировать его таким образом, чтобы C++
Преобразовать массив таким образом, чтобы элементы, равные нулю располагались после остальных. C++
В файл вставить пробелы таким образом, чтобы каждая строка имела длину 80 символов C++
C++ Реализовать процедуру таким образом, чтобы она возвращала 2 значения
Преобразовать строку таким образом, чтобы все слова в ней были напечатаны наоборот C++
Распределить числа в два массива так, чтобы разность между их суммами была минимальной C++
C++ Модифицировать программу таким образом, чтобы класс содержал закрытые переменные
C++ Преобразовать строку таким образом, чтобы все слова в ней были напечатаны наоборот
Переставить каждую пару строк матрицы таким образом, чтобы первой была строка с меньшей суммой элементов C++
Распределить камни в две кучи так, чтобы разность весов этих двух куч была минимальной C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 12:54. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru