Форум программистов, компьютерный форум 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
Супер-модератор
Эксперт С++
5603 / 2637 / 242
Регистрация: 01.11.2011
Сообщений: 6,496
Завершенные тесты: 1
07.12.2012, 11:54     Найти площадь крупнейшего сплошного прямоугольника суши
Цитата Сообщение от 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, с тебя пиво.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru