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

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

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

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

30.06.2009, 20:55. Просмотров 740. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.06.2009, 20:55     Площадь наибольшего из прямоугольников матрицы
Посмотрите здесь:

Найти площадь общей части прямоугольников C++
C++ Найти площадь пересечения прямоугольников
C++ Последовательно вводятся габариты n прямоугольников. Определить площадь их пересечения.
Найти площадь фигуры, получающейся в результате объединения прямоугольников C++
C++ Определить, площадь какого из прямоугольников минимальна
C++ Найти периметр и площадь пяти прямоугольников по известным сторонам
C++ Определить площадь фигуры, образованной объединением прямоугольников
Площадь пересечения двух прямоугольников C++
C++ Площадь пересечения двух прямоугольников
Площадь пересечения прямоугольников C++
C++ Задачка на нахождения числа прямоугольников площадь которых больше D
C++ Найти площадь пересечения, то есть общую часть двух прямоугольников (не могу понять алгоритм решения)

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vourhey
Почетный модератор
6473 / 2248 / 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 нуля, например, вторым элементом, то этот прямоугольник тебе нужно будет досчитать уже по самой короткой стороне. По сути тебе нужно хранить в переменных только самую короткую высоту, что ты нашла и то, сколько столбцов ты прошла, и индекс строки, с которой ты считаешь. Плюс надо помнить, что прямоугольник может начинаться не только со строки, с которой ты начинаешь считать, но и с любого места меньше найденной тобою высоты.
Этот алгоритм легко реализовать.
Immes
0 / 0 / 0
Регистрация: 23.01.2009
Сообщений: 13
01.07.2009, 16:48  [ТС]     Площадь наибольшего из прямоугольников матрицы #3
Если честно, то я целый день пыталась его реализовать, но так и не смогла.
TanT
эволюционирую потихоньку
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
04.07.2009, 18:25     Площадь наибольшего из прямоугольников матрицы #4
Я нарисовал примерно. Похожее когда-то на экзамене было. весёлая задачка. исходники могу выложить. тока в условиях задачи не сказанно, как поступать, если несколько прямоугольников одинаковой площади. У меня надо было все учесть.
TanT
эволюционирую потихоньку
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
05.07.2009, 06:07     Площадь наибольшего из прямоугольников матрицы #5
Вот...
Вложения
Тип файла: txt Rectangle.txt (5.9 Кб, 58 просмотров)
Yandex
Объявления
05.07.2009, 06:07     Площадь наибольшего из прямоугольников матрицы
Ответ Создать тему
Опции темы

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