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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
Taras_Z
 Аватар для Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
29.11.2012, 14:01     Найти площадь крупнейшего сплошного прямоугольника суши #1
Наибольшая площадь
Территория состоит из квадратиков суши (обозначены единичками) и воды (обозначены ноликами). Найти площадь крупнейшего сплошного прямоугольника суши.
В файле данных "land.txt" в первой ленте размеры территории.
Далее - карта территории.
Пример входных даих
7 8
01110111
11110111
11111101
11111101
01111111
10111111
11011111

ответ
16

Добавлено через 19 часов 30 минут
upupupup
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.11.2012, 14:01     Найти площадь крупнейшего сплошного прямоугольника суши
Посмотрите здесь:

C++ периметр и площадь прямоугольника
Площадь прямоугольника C++
Найти площадь, лежащую в первой координатной четверти, прямоугольника, заданного вершинами. C++
Площадь прямоугольника C++
Найти площадь прямоугольника C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
NeonLost
Пес войны
 Аватар для NeonLost
74 / 85 / 3
Регистрация: 23.02.2012
Сообщений: 653
29.11.2012, 15:52     Найти площадь крупнейшего сплошного прямоугольника суши #2
хоть убей, не вижу прямоугольника из 16 единиц(
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,333
Завершенные тесты: 1
29.11.2012, 16:13     Найти площадь крупнейшего сплошного прямоугольника суши #3
NeonLost,
01110111
11110111
11111101
11111101
01111111
10111111
11011111
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,333
Завершенные тесты: 1
04.12.2012, 10:56     Найти площадь крупнейшего сплошного прямоугольника суши #4
Три дня думал над алгоритмом, и что-то ничего не придумывается.
Ну давай тогда рассуждать. Смотри. Самое первое что приходит на ум это огромным количеством вложенных циклов замерить расстояние от каждой единицы до нуля (или края области) во всех четырех направлениях. Таким образом мы узнаем какую-то величину, назовем ее, к примеру, вес единицы. Посмотрим что это нам даст.

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

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













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

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









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


Была еще одна мысль в другую сторону, другой алгоритм:
находить нули, от них во все стороны проводить линии, которые будут образовывать прямоугольники, определять их углы и замерять площадь. Но как это реализовать я еще не придумал.
Можно пока обсудить первый вариант.
Надеюсь хоть как-то помог.
v.a.l.i.d
 Аватар для v.a.l.i.d
412 / 377 / 10
Регистрация: 21.09.2012
Сообщений: 913
04.12.2012, 13:18     Найти площадь крупнейшего сплошного прямоугольника суши #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include "stdafx.h"
#include "windows.h"
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL, "Russian");
 
    const int ROWS=7, COLS=8;
    int A[ROWS][COLS] = 
    {
        {0,1,1,1,0,1,1,1}, 
        {1,1,1,1,0,1,1,1},
        {1,1,1,1,1,1,0,1},
        {1,1,1,1,1,1,0,1},
        {0,1,1,1,1,1,1,1},
        {1,0,1,1,1,1,1,1},
        {1,1,0,1,1,1,1,1},
    };
    int Area[ROWS][COLS] = {0}; // массив площадей
    int max_area = 0;
 
    for (int y=0; y<ROWS; y++)
        for (int x=0; x<COLS; x++)
        {
            for (int yy=x; yy<ROWS; yy++)
                for (int xx=x; xx<COLS; xx++)
                    if (A[yy][xx] == 0)
                    {
                        if ((xx+1-x)*(yy+1-y) > Area[y][x])
                            Area[y][x] = (xx+1-x)*(yy+1-y);
 
                        goto nextX;
                    }
 
            for (int xx=x; xx<COLS; xx++)
                for (int yy=y; yy<ROWS; yy++)
                    if (A[yy][xx] == 0)
                    {
                        if ((xx+1-x)*(yy-1-y) > Area[y][x])
                            Area[y][x] = (xx+1-x)*(yy+1-y);
 
                        goto nextX;
                    }
 
            nextX: ;
        }
 
    for (int y=0; y<ROWS; y++)
        for (int x=0; x<COLS; x++)
            if (Area[y][x] > max_area)
                max_area = Area[y][x];
 
    cout << "Наибольшая площадь суши " << max_area << endl;
 
    system("pause");
    return 0;
}
Добавлено через 1 час 20 минут
неправильная у меня программа. сейчас проверил и что-то не сходится.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,333
Завершенные тесты: 1
04.12.2012, 13:40     Найти площадь крупнейшего сплошного прямоугольника суши #6
Цитата Сообщение от V.A.L.I.D Посмотреть сообщение
неправильная у меня программа. сейчас проверил и что-то не сходится.
На словах хоть поясни, пожалуйста.
v.a.l.i.d
 Аватар для v.a.l.i.d
412 / 377 / 10
Регистрация: 21.09.2012
Сообщений: 913
04.12.2012, 13:55     Найти площадь крупнейшего сплошного прямоугольника суши #7
Цитата Сообщение от SatanaXIII Посмотреть сообщение
На словах хоть поясни, пожалуйста.
вообщем искал первый элемент массива который равен нулю по Х и по У справа и внизу от текущей клетки и потом искал площадь. вообще направильно работает. хотя первый раз результат получился правильным - 16
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,333
Завершенные тесты: 1
04.12.2012, 14:06     Найти площадь крупнейшего сплошного прямоугольника суши #8
Цитата Сообщение от V.A.L.I.D Посмотреть сообщение
вообщем искал первый элемент массива который равен нулю по Х и по У справа и внизу от текущей клетки и потом искал площадь.
Это вот второй как раз метод, который я думал.
Только.
Надо как только нашел первый ноль (первый угол прямоугольника) останавливать цикл и искать второй ноль, который будет дальше (по проходу) (второй угол). И потом до него мерить прямоугольник. Как только до всех вторых углов промерено, сдвинуть на следующий ноль первый угол.
Но так не пойдет. Так как углы прямоугольника могут находиться и не в самом нуле.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,333
Завершенные тесты: 1
04.12.2012, 14:48     Найти площадь крупнейшего сплошного прямоугольника суши #9
Ах-ха-ха-ха-ха! (гомерический смех) Ну что за тупизм.
Придумал.
Сначала подумалось, что раз такая пьянка, то почему бы и не перебирать вообще ВСЕ прямоугольники, и смотреть заполнены ли они единицами. Почему бы и нет. Так меньше проходов получится. по сути это двойной проход по всей площади: сначала один угол стоит, а второй пробегает все значения, потом первый угол сдвигается на один элемент, второй при этом опять пробегает все значения. Это два цикла. А третий, самый вложенный уже проверяет выбранную площадь от одного угла до другого на полное заполнение единицами.

Фигня! Круче способ:
1) Один главный проход по всем элементам всей области слева направо, сверху вниз.
2) Если попадается единица, от нее (Mas[i,j]) вправо отсчитываем до первого встретившегося нуля (или края области). Запоминаем (x). От нее же отсчитываем вниз до нуля (края). Запоминаем (y).
3) Двойной цикл от j до y и от i до x: перебираем область. Если нули не встречаются, тогда запоминаем площадь и координаты сектора. Если встречается ноль, то сравниваем что меньше текущее значение от j до y или от i до x (грубо говоря мы по строке дальше сдвинулись вправо или по столбцу опустились). Соответственно запоминаем наибольшее значение для площади.
4) Сравниваем с предыдущим наибольшим значением.

Название: 5555.JPG
Просмотров: 186

Размер: 5.6 Кб

Красный квадрат - текущий элемент.
Красные стрелки - проход вправо и вниз.

Синий квадрат - общая область для этого элемента.

Зеленый овал - полученная область.
Зеленые стрелки - обход выбранной области.
v.a.l.i.d
 Аватар для v.a.l.i.d
412 / 377 / 10
Регистрация: 21.09.2012
Сообщений: 913
04.12.2012, 15:35     Найти площадь крупнейшего сплошного прямоугольника суши #10
SatanaXIII, Осталось программу написать
Taras_Z
 Аватар для Taras_Z
100 / 84 / 2
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
05.12.2012, 19:11  [ТС]     Найти площадь крупнейшего сплошного прямоугольника суши #11
Спасибо большое за старание!
Только одно: если можно напишите код на с++, а то я щас немогу ни на чем писать, так как ноуту капец, а здавать надо через день.
v.a.l.i.d
 Аватар для v.a.l.i.d
412 / 377 / 10
Регистрация: 21.09.2012
Сообщений: 913
05.12.2012, 19:24     Найти площадь крупнейшего сплошного прямоугольника суши #12
Если до завтра никто не решит то утром тогда посмотрю. Но ничего не обещаю. Задача уж больно сложная
Schizorb
 Аватар для Schizorb
508 / 460 / 16
Регистрация: 07.04.2012
Сообщений: 865
Записей в блоге: 1
Завершенные тесты: 1
05.12.2012, 20:43     Найти площадь крупнейшего сплошного прямоугольника суши #13
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
 
int main()
{   
    const int rows = 7, cols = 8;
 
    int arr[rows][cols] = 
    {
        {0,1,1,1,0,1,1,1}, 
        {1,1,1,1,0,1,1,1},
        {1,1,1,1,1,1,0,1},
        {1,1,1,1,1,1,0,1},
        {0,1,1,1,1,1,1,1},
        {1,0,1,1,1,1,1,1},
        {1,1,0,1,1,1,1,1},
    };
 
    int i, j, k, jj, ii;
    int square, max_square = 0;
    bool find_null;
    
    for(i = 0; i < rows; ++i)
    {
        for(j = 0; j < cols; ++j)
        {
            std::cout << arr[i][j] << " ";
        }
        std::cout << "\n";
    }
    std::cout << "\n\n";
    
    for(i = 0; i < rows; ++i)
    {
        for(j = 0; j < cols; ++j)
        {
            if(arr[i][j] == 1)
            {
                jj = j + 1;
                
                while(arr[i][jj] == 1 && jj < cols)
                {   
                    ++jj;
                } 
                
                ii = i + 1;
                      
                find_null = false;
                
                while(ii < rows)
                {
                    for(k = jj - 1; k >= j; --k)
                    {
                        if(arr[ii][k] == 0)
                        {
                            find_null = true;
                            break;
                        }    
                    }
                    if(find_null)
                        break;
                        
                    ++ii;                  
                }
                
                square = (jj - j) * (ii - i);
 
                if(square > max_square)
                    max_square = square;    
            }
        }
        
    }
    
    std::cout << "Max square = " << max_square << "\n";
    
    return 0;
}
Возможно решение не самое удачное и запутанное. Принцип примерно такой:
*Просматриваем все элементы в цикле.
*Если встречаем 1, то считаем единицы справа от нее до нуля (находим горизонтальную строчку единиц).
*Переходим на строку ниже и проверяем соответствующий диапазон столбцов, если встречаем 0 - прекращаем подсчет, иначе проверяем следующую строку (в цикле).

Особо не тестировал)
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,333
Завершенные тесты: 1
07.12.2012, 11:54     Найти площадь крупнейшего сплошного прямоугольника суши #14
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от V.A.L.I.D Посмотреть сообщение
Осталось программу написать
Цитата Сообщение от Taras_Z Посмотреть сообщение
если можно напишите код на с++
Исполняю.



Алгоритм:
1) Двойной цикл (i, j) - перебор всех элементов области.

Найти площадь крупнейшего сплошного прямоугольника суши
2) От каждого [i][j]-го элемента два цикла - проходы вправо и вниз. До нуля или края области.
Получив два значения смещения (ShiftDown и ShiftRight) высчитывается площадь, допустимая для данного прямоугольника. Если она оказалась больше предыдущей запомненной, то смотрим вся ли они состоит из единиц (то есть не нулей), есть ли в ней нули.

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








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

Если перебираем построчно, то, найдя ноль, уменьшаем счетчик строк (countY-1)
Во втором цикле соответственно счетчик столбцов (countX-1).

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

Если ноль не встретился, то запоминаем наибольшую площадь для этого прямоугольника:
(LastAngleX-FirstAngleX)+1)*((LastAngleY-FirstAngleY)+1
Прибавление единицы здесь нужно из-за того, что размерность массива начинается с нуля. Чтобы при умножении не получить нулевую площадь заместо площади шириной в один столбец (строку).

В итоге имеем координаты прямоугольника и его площадь.


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <iostream.h>
 
 
int main(int argc, char* argv[])
{
 
const int r=7, c=8;
int Mas[r][c]={ {0 ,12,13,14,0 ,16,17,18},
                {21,22,23,24,0 ,26,27,28},
                {31,32,33,34,35,36,0 ,38},
                {41,42,43,44,45,46,0 ,48},
                {0 ,52,53,54,55,56,57,58},
                {61,0 ,63,64,65,66,67,68},
                {71,72,0 ,74,75,76,77,78} };
 
 
for(int i=0; i<r; i++)
  {
  for(int j=0; j<c; j++)
    {
    if(!Mas[i][j])cout<<" ";
    cout << Mas[i][j] << " ";
    }
  cout << endl;
  }
 
 
 
int ShiftRight, ShiftDown;    // Смещение вправо и вниз
int FirstAngleX, FirstAngleY; // Левый верхний угол
int LastAngleX, LastAngleY;   // Правый нижний угол
int Square=0;                 // Площадь
 
 
for(int i=0; i<r; i++)
  for(int j=0; j<c; j++)
    {
    if(Mas[i][j])
      {
      for(ShiftDown=i; Mas[ShiftDown+1][j]&&ShiftDown<r-1; ShiftDown++);     // Определяем сколько единиц вниз
      for(ShiftRight=j; Mas[i][ShiftRight+1]&&ShiftRight<c-1; ShiftRight++); // Определяем сколько единиц вправо
 
      if(Square<(((ShiftDown-i+1))*((ShiftRight-j+1)))) // Берем площадь прямоугольника
        {
        bool ZeroExist = false;
 
        bool EndFlag=false;                       // И смотрим есть ли в нем нули
        for(int countY=i; (countY<=ShiftDown)&&(!EndFlag); countY++) // Горизонтальный проход
          for(int countX=j; countX<=ShiftRight; countX++)
            {
            if(!Mas[countY][countX]) // Если ноль найден
              {
              ZeroExist = true;
              if(Square<((countY-i)*(ShiftRight-j+1))) // Проверка: больше ли текущая площадь чем запомненной
                {
                FirstAngleX=j; // Запоминаем координаты
                FirstAngleY=i; //  левого верхнего угла
 
                LastAngleX=ShiftRight; // Запоминаем кардинаты
                LastAngleY=countY-1;   //  правого нижнего угла
                Square=((countY-i)*(ShiftRight-j+1)); // Запоминаем площадь
                }
              EndFlag=true; // Выходим из обоих циклов
              break;        // то есть заканчиваем горизонтальный проход
              }
            }
 
        EndFlag=false;
        for(int countX=j; (countX<=ShiftRight)&&(!EndFlag); countX++) // Вертикальный проход
          for(int countY=i; countY<=ShiftDown; countY++)
            {
            if(!Mas[countY][countX])
              {
              ZeroExist = true;
              if(Square<((countX-j)*(ShiftDown-i+1)))
                {
                FirstAngleX=j;
                FirstAngleY=i;
 
                LastAngleX=countX-1;
                LastAngleY=ShiftDown;
                Square=((countX-j)*(ShiftDown-i+1));
                }
              EndFlag=true;
              break;
              }
            }
 
        if(ZeroExist==false) // Если текущий прямоугольник не содержит нулей
          {
          FirstAngleX=j;
          FirstAngleY=i;
          LastAngleX=ShiftRight;
          LastAngleY=ShiftDown;
          Square=((LastAngleX-FirstAngleX)+1)*((LastAngleY-FirstAngleY)+1);
          }
 
          /*cout<<endl<<" Mas["<<i<<"]["<<j<<"]="<<Mas[i][j];
          cout<<endl<<" FirstAngleX="<<FirstAngleX;
          cout<<      " FirstAngleY="<<FirstAngleY;
          cout<<endl<<" LastAngleX="<<LastAngleX;
          cout<<      " LastAngleY="<<LastAngleY;
          cout<<" Square="<<Square;*/
 
        }//
 
      }
    }
 
cout<<endl<<endl;
 
/*for(int i=0; i<r; i++) // Вывод
  {
  for(int j=0; j<c; j++)
    {
    if(i>=FirstAngleY && i<=LastAngleY &&
       j>=FirstAngleX && j<=LastAngleX)
       cout<<"!";
 
 
    if(!Mas[i][j])cout<<" ";
    cout << Mas[i][j] << " ";
    }
  cout << endl;
  }*/
for(int i=0; i<r; i++)
  {
  for(int j=0; j<c; j++)
    {
    if(!Mas[i][j])cout<<" ";
 
    if(i>=FirstAngleY && i<=LastAngleY &&
       j>=FirstAngleX && j<=LastAngleX)
       cout<<"!! ";
    else
    cout << Mas[i][j] << " ";
    }
  cout << endl;
  }
 
 
 
 
 
cout<<endl<<"Ploshad="<<Square;
cin.ignore();
 
        return 0;
}
P.S. Taras_Z, с тебя пиво.
BRcr
01.11.2014, 13:26
  #15

Не по теме:

Неоцененный труд, однако.

gng
605 / 451 / 122
Регистрация: 08.09.2013
Сообщений: 1,152
02.11.2014, 23:40     Найти площадь крупнейшего сплошного прямоугольника суши #16
SatanaXIII, а с такими данными выдает 16 вместо 20
7 8
01110111
11111111
11111101
11111101
01111111
10111111
11011111
Предложу свой вариант, вроде бы работает.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <string.h>
#include <malloc.h>
 
int main() {
  int M, N;
  scanf ("%d %d\n", &M, &N);
  char *a= (char*)malloc (M * N + 2);
  for (char *p= a; p < a + M*N; p+= N) fgets (p, N+2, stdin);
 
  int max= 0;
  for (char *p = a;  p < a+ M*N; p++) {
    for (int k=1; k <= (a+M*N-p-1)%N+1; k++) {
      if (*(p+k-1) == '0') break;
      int s= k;
      for (char *t= p + N; t < a + M*N; t+=N) {
        if (strncmp (p, t, k)) break;
        s+= k;
      }
      if (max < s) max= s;
    }
  }
  printf ("%d\n", max);
  free (a);
  return 0;
}
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
03.11.2014, 01:20     Найти площадь крупнейшего сплошного прямоугольника суши #17
http://e-maxx.ru/algo/maximum_zero_submatrix
gng
605 / 451 / 122
Регистрация: 08.09.2013
Сообщений: 1,152
03.11.2014, 13:22     Найти площадь крупнейшего сплошного прямоугольника суши #18
SlavaSSU, неплохой алготитм.
Для интереса сравнил время подсчета со своим, приведенным выше для матрицы из 30 млн элементов (5000x6000).
Мой сделал за 2с, ваш - за 12с, результаты совпали. Но поскольку мой считает в лоб - O(n2m2), то для огромных матриц ваш, видимо, будет быстрее. Хотя и в моем остается немалый простор для оптимизации даже в рамках текущего алгоритма.

Добавлено через 3 часа 36 минут
Неполенился проверить для других соотношений нулей и единиц. Прошлый тест проводился для 1:1
Начиная с соотношения 7:1 ваша программа уверенно вырывается вперёд. Ответы остаются одинаковыми, что наталкивает на мысль, что обе программы считают правильно.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,333
Завершенные тесты: 1
10.11.2014, 08:55     Найти площадь крупнейшего сплошного прямоугольника суши #19
Цитата Сообщение от gng Посмотреть сообщение
а с такими данными выдает 16 вместо 20
Однако, клевета:
Миниатюры
Найти площадь крупнейшего сплошного прямоугольника суши  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.11.2014, 23:41     Найти площадь крупнейшего сплошного прямоугольника суши
Еще ссылки по теме:

Дана гипотенуза с, и угол альфа прямоугольника, найти площадь и периметр C++
Даны стороны прямоугольника a и b Найти его площадь S и периметр P C++
C++ Найти длину диагонали, периметр и площадь прямоугольника, зная длины его сторон

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

Или воспользуйтесь поиском по форуму:
gng
605 / 451 / 122
Регистрация: 08.09.2013
Сообщений: 1,152
10.11.2014, 23:41     Найти площадь крупнейшего сплошного прямоугольника суши #20
Цитата Сообщение от SatanaXIII Посмотреть сообщение
Однако, клевета:
Признаю свою ошибку, я просмотрел другой алгоритм (из поста #13) и это он выдает 16 вместо 20.
Ваш на массиве 2000x4000 выдал ошибку сегментирования. Если не пропал интерес, скорректируйте код, чтобы читал входные данные, как в условии задачи. Я прогоню на эффективность.
Yandex
Объявления
10.11.2014, 23:41     Найти площадь крупнейшего сплошного прямоугольника суши
Ответ Создать тему

Метки
площадь
Опции темы

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