Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 23.01.2009
Сообщений: 13
1

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

30.06.2009, 20:55. Просмотров 1047. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.06.2009, 20:55
Ответы с готовыми решениями:

Среди прямоугольников матрицы, состоящих из нулей, найти тот, который имеет наибольшую площадь
Помогите решить задачу Дана целочисленная матрица i=1 ,..., n ; j=1 ,..., m . Прямоугольником...

Определить площадь 30 прямоугольников
Определить площадь 30 прямоугольников. Сторона a первого равна 4 см, а сторона b 7 см. Сторона...

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

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

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

Забыл указать. Если у тебя единичка встретится, раньше, чем ты отсчитаешь 3 нуля, например, вторым элементом, то этот прямоугольник тебе нужно будет досчитать уже по самой короткой стороне. По сути тебе нужно хранить в переменных только самую короткую высоту, что ты нашла и то, сколько столбцов ты прошла, и индекс строки, с которой ты считаешь. Плюс надо помнить, что прямоугольник может начинаться не только со строки, с которой ты начинаешь считать, но и с любого места меньше найденной тобою высоты.
Этот алгоритм легко реализовать.
0
0 / 0 / 0
Регистрация: 23.01.2009
Сообщений: 13
01.07.2009, 16:48  [ТС] 3
Если честно, то я целый день пыталась его реализовать, но так и не смогла.
0
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
04.07.2009, 18:25 4
Я нарисовал примерно. Похожее когда-то на экзамене было. весёлая задачка. исходники могу выложить. тока в условиях задачи не сказанно, как поступать, если несколько прямоугольников одинаковой площади. У меня надо было все учесть.
0
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
05.07.2009, 06:07 5
Вот...
1
Вложения
Тип файла: txt Rectangle.txt (5.9 Кб, 66 просмотров)
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.07.2009, 06:07

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

площадь объединения прямоугольников
Требуется код или алгоритм, позволяющий считать площадь объединения прямоугольников. Стороны...

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

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

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


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

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