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

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

Восстановить пароль Регистрация
 
ivy
0 / 0 / 0
Регистрация: 22.12.2013
Сообщений: 8
22.12.2013, 18:30     Выбирать поле таким образом, чтобы необходимая площадь для разворота суммарно была минимальной #1
прошу помощи в решении задачи
сабж:
Кликните здесь для просмотра всего текста
Пусть имеется прямоугольное поле размерами 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++
C++ Реализовать процедуру таким образом, чтобы она возвращала 2 значения
C++ Модифицировать программу таким образом, чтобы класс содержал закрытые переменные
Преобразовать строку таким образом, чтобы все символы в ней были напечатаны наоборот C++
C++ Преобразовать строку таким образом, чтобы все слова в ней были напечатаны наоборот

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

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

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