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

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

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

Площадь наибольшего из прямоугольников матрицы - C++

30.06.2009, 20:55. Просмотров 762. Ответов 4
Метки нет (Все метки)

Дана целочисленная матрица A[i][j];i=1,n;j=1,m. Прямоугольником в этой матрице будем называть множество всех элементов A[i][j], для которых выполнено 1<=p<=i<=q<=n, 1<=r<=j<=s<=m, где p,q,r,s - натуральные числа, задающие прямоугольник. Площадью прямоугольника назовём число элементов в нём. Среди прямоугольников матрицы,состоящих целиком из нулей, найти тот, который имеет наибольшую площадь.

Если бы не было мне сказано условия, что прямоугольники могут пересекаться, то я бы сделала. Но это условие поставило меня в тупик... Как можно найти p,q,r и s, если матрица выглядит к примеру так:

1 0 0 1 1 1 1
1 0 0 1 1 1 1
1 0 0 0 0 1 1
1 1 0 0 0 1 1
1 1 1 1 1 1 1
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.06.2009, 20:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Площадь наибольшего из прямоугольников матрицы (C++):

Площадь пересечения прямоугольников - C++
Здравствуйте. Мне нужно найти площадь пересечения двух прямоугольников, если известны координаты данных прямоугольников. Стороны одного...

Площадь пересечения двух прямоугольников - C++
Даны 4 координаты: 2 из них - координаты противоположных вершин первого прямоугольника (не известно каких) и оставшиеся две -...

Найти площадь пересечения прямоугольников - C++
даны 2 прямоугольника. Каждый из них задан 2 точками. верхней левой и правой нижней. если они пресекаются найди их площадь... Задавать надо...

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

Найти площадь общей части прямоугольников - C++
На плоскости нарисованы два прямоугольника П1 и П2, стороны которых параллельны осям координат. Найти площадь S общей части прямоугольников...

Определить, площадь какого из прямоугольников минимальна - C++
Даны длины сторон трех прямоугольников. Определить, площадь какого из прямоугольников минимальна. Нахождение площади прямоугольника и...

4
Vourhey
Почетный модератор
6482 / 2256 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
30.06.2009, 21:34 #2
Ну, допустим, мы будем считать, для начала, по столбцам. Иду по первой строке до первого нолика. Это элемент a[0][1]. Потом по столбику вниз иду до единицы, считая элементы. Отлично. Высота прямоугольника мне уже известна. Она равна трем. Теперь, иду в следующий столбик [2] и от элемента a[0][2] также вниз до первой единицы или до того, как высота будет равна трем (мы же ее нашли на предыдущем шаге). таким, образом мы остановились на элементе a[2][2]. Дальше идем в следующий столбик, но там a[0][3] стоит единица. Значит, с первым прямоугольником у нас закончено.
И так далее для остальных столбцов. Может, есть способ удобнее, я пока не придумал )

Забыл указать. Если у тебя единичка встретится, раньше, чем ты отсчитаешь 3 нуля, например, вторым элементом, то этот прямоугольник тебе нужно будет досчитать уже по самой короткой стороне. По сути тебе нужно хранить в переменных только самую короткую высоту, что ты нашла и то, сколько столбцов ты прошла, и индекс строки, с которой ты считаешь. Плюс надо помнить, что прямоугольник может начинаться не только со строки, с которой ты начинаешь считать, но и с любого места меньше найденной тобою высоты.
Этот алгоритм легко реализовать.
0
Immes
0 / 0 / 0
Регистрация: 23.01.2009
Сообщений: 13
01.07.2009, 16:48  [ТС] #3
Если честно, то я целый день пыталась его реализовать, но так и не смогла.
0
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
04.07.2009, 18:25 #4
Я нарисовал примерно. Похожее когда-то на экзамене было. весёлая задачка. исходники могу выложить. тока в условиях задачи не сказанно, как поступать, если несколько прямоугольников одинаковой площади. У меня надо было все учесть.
0
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
05.07.2009, 06:07 #5
Вот...
1
Вложения
Тип файла: txt Rectangle.txt (5.9 Кб, 59 просмотров)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.07.2009, 06:07
Привет! Вот еще темы с ответами:

Определить площадь фигуры, образованной объединением прямоугольников - C++
Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить площадь фигуры, образованной объединением данных...

Последовательно вводятся габариты n прямоугольников. Определить площадь их пересечения. - C++
Площади прямоугольников. Прямоугольник на плоскости a&lt;=x&lt;=b; c&lt;=y&lt;=d задается четырьмя числами (его габаритами): a,b,c,d. Последовательно...

Задачка на нахождения числа прямоугольников площадь которых больше D - C++
Каждой парой (Xk, Yk) заданы длины сторон одного из прямоугольников; найти число тех прямоугольников, площадь которых больше D. Не могу...

Аналитическая геометрия. Площадь фигуры, образованной объединением прямоугольников - C++
Условие: даны координаты противоположных углов прямоугольников, найти площадь фигуры, образованной объеденением прямоугольников. Я думаю,...


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

Или воспользуйтесь поиском по форуму:
5
Yandex
Объявления
05.07.2009, 06:07
Ответ Создать тему
Опции темы

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