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

Найти площадь крупнейшего сплошного прямоугольника суши - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Ошибка при компиляции(Тестирование памяти) http://www.cyberforum.ru/cpp-beginners/thread712291.html
error C3861: 'ReadMemory': identifier not found(на MSDN написано что нужно подключить то та-то) Подключаю одну из двух написанных(If you are writing a WdbgExts extension, include wdbgexts.h. If you are writing a DbgEng extension that calls this function, include wdbgexts.h before dbgeng.h) wdbgexts.h- подключаю пишет ": fatal error C1083: Cannot open include file: 'wdbgexts.h': No such file...
C++ Нахождение разных чисел в массиве помогите пожалуйста пересести на с++ program p3; uses crt; var a:array of integer; i,j,n,z,l:integer; begin http://www.cyberforum.ru/cpp-beginners/thread712287.html
C++ Упорядочить строки матрицы по возрастанию их первых элементов
В работе память для массива должна выделяться динамически. На экран выводить исходные данные и результат. Дана матрица размером NxM. Упорядочить ее строки по возрастанию их первых элементов. #include "iostream.h" #include "iomanip.h" #include "math.h"
Сумма ряда C++
Вычислить сумму первых n членов ряда, где n-ный член ряда вычисляется по формуле (x^n)/n. Суть проблемы: дальше определённого значения вычисления не идут. Например, для числа 2 сумма не получается больше 6.389057, для 3 - больше 19.085539, и т.д. #include <stdio.h> #include <conio.h> int main() { int i=1, n; float x, sum=0, xn=1;
C++ создание классов http://www.cyberforum.ru/cpp-beginners/thread712280.html
Создать класс Зачет, имеющий поля: название предмета, зачет (лог. поле). Создать производный класс Экзамен, имеющий поле оценка
C++ можно ли считать данный код реализацией очереди можно ли считать данный код реализацией очереди. и если нет, то почему. #include <stdlib.h> #include <stdio.h> typedef struct LIST{ int val; struct LIST *ptr; }; подробнее

Показать сообщение отдельно
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2563 / 233
Регистрация: 01.11.2011
Сообщений: 6,337
Завершенные тесты: 1
04.12.2012, 10:56     Найти площадь крупнейшего сплошного прямоугольника суши
Три дня думал над алгоритмом, и что-то ничего не придумывается.
Ну давай тогда рассуждать. Смотри. Самое первое что приходит на ум это огромным количеством вложенных циклов замерить расстояние от каждой единицы до нуля (или края области) во всех четырех направлениях. Таким образом мы узнаем какую-то величину, назовем ее, к примеру, вес единицы. Посмотрим что это нам даст.

Найти площадь крупнейшего сплошного прямоугольника суши
Берем и проходим перебором по всем элементам области (на рисунке красный квадрат).
От каждого элемента по четыре цикла (вверх, вниз, влево, вправо).
Таким образом получаем для каждой единицы четверку значений.

Для текущего элемента (на картинке):
Верх : 2;
Низ: 3;
Лево: 2;
Право: 3;













Составив такие четверки для каждого элемента получим (для наглядности) таблицу:
Слева таблица непосредственно четверок (в порядке: лево, право, верх, низ), а справа просуммированные значения четверок.
Найти площадь крупнейшего сплошного прямоугольника суши Найти площадь крупнейшего сплошного прямоугольника суши
В принципе существует закономерность между величиной суммы и площадью, занимаемой прямоугольником: чем больше значение суммы, тем в более обширный прямоугольник входит единица.
Но четкого определения нет.

Найти площадь крупнейшего сплошного прямоугольника суши
Далее, если следовать той же логике, нужно каким-то образом усреднить значения сумм четверок, чтобы в идеале все единицы наибольшего прямоугольника имели одинаковый меж собой и наибольший меж не входящими в прямоугольник элементами. Тогда все станет просто. Но вот как сделать это просто?
Я вот думал в сторону если запустить от каждого элемента еще по четыре цикла (так же вверх, вниз, влево, вправо) и на каждой итерации еще по два цикла под девяносто градусов от текущего направления. На картинке слева представлен один только проход вниз. Синие цифры и круглые стрелки - итерации прохода вниз. (нулевая итерация - от красного квадрата) Плоские стрелки это дополнительные проходы влево и вправо на каждой итерации спуска вниз.
Смысл:
Рассмотрим вторую итерацию (кружок с цифрой 2)
Движемся от него вправо и проверяем текущее значение со значением "право" из четверки предыдущего элемента. Видим, что на четвертом шаге вправо мы превысили значение вправо для предыдущего элемента. На этом проход вправо прерываем и текущему элементу (кружок с 2) присваиваем в его четверку в значение "право"текущий результат цикла минус один. По сути то же самое значение, что и у элемента выше.
При проходе же влево (то есть когда у нас значения становятся постоянно меньше текущего) надо найти самое минимальное значение среди всех и всей вертикали (можно обратным циклом) присвоить его.









Вот что-то как-то так. Что из этого получится одному богу известно. Но можешь попробовать.


Была еще одна мысль в другую сторону, другой алгоритм:
находить нули, от них во все стороны проводить линии, которые будут образовывать прямоугольники, определять их углы и замерять площадь. Но как это реализовать я еще не придумал.
Можно пока обсудить первый вариант.
Надеюсь хоть как-то помог.
 
Текущее время: 15:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru