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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
DAgot_
22 / 22 / 1
Регистрация: 03.01.2010
Сообщений: 68
#1

Максимальная площадь прямоугольника из матрицы. - C++

15.02.2010, 18:04. Просмотров 1764. Ответов 9
Метки нет (Все метки)

Помогите, пожалуйста, никак не могу понять, что не так.

Есть матрица чисел заполненная нулями и единицами.
Нужно найти прямоугольник, состоящий из нулей и обладающий максимальной площадью.

Вот мой код (рабочий):
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
/* Описание:    Данная программа предназначена для поиска в текстовом
                файле прямоугольника, целиком состоящего из нулей,
                с максимальной площадью. */
 
/*............................ЗАГОЛОВОЧНЫЕ ФАЙЛЫ.............................*/
 
#include <stdio.h>
#include <iostream>
using namespace std;
 
/*.........................МОДУЛИ, ДЕФАЙНЫ И ПРОЧЕЕ..........................*/
 
#define WIDTH 10
#define HEIGHT 10
 
/*...............................ТОЧКА ВХОДА.................................*/
 
int main(){
 
    FILE *input=fopen("input.txt","r");    // Открыть файл "input.txt"на чтение.
 
    int Mas[WIDTH][HEIGHT];    // Объявление массива (с ним мы и работаем).
    int Area=0, MaxArea=0;    // Объявление переменных "Площадь", "Макс. Площадь".
    int CurI, CurJ;
    int Width=0, Height=0;
 
    /* Считываем данные из файла "input.txt" в массив. */
    for(int i=0;i<HEIGHT;i++){
        for(int j=0;j<WIDTH;j++){
            fscanf(input,"%d",&Mas[i][j]);
        }
    }
    /* Находим в массиве прямоугольник из нулей с максимальной площадью. */
    for(int l=0;l<HEIGHT;l++){
        for(int k=0;k<WIDTH;k++){
            
            CurI=l;
            CurJ=k;
            
            while (Mas[CurI][CurJ]==0){
                CurJ++;
                Width++;
            }
            
            CurI=l;
            CurJ=k;
            
            while (Mas[CurI][CurJ]==0){
                CurI++;
                Height++;
            }
            Area=Width*Height;
 
            if(MaxArea<Area)
                MaxArea=Area;
 
            Area=0;
            Width=0;
            Height=0;
        }
    }
    
    cout << "     TA-DA!" << "\n\n";
    cout << "Maximum Area = " << MaxArea << "\n\n";
    return 0;
}

Его нужно переделать его так, чтоб память под массив выделялась динамически.
Я наваял вот это, но оно не работает:
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
/* Описание:    Данная программа предназначена для поиска в текстовом
                файле прямоугольника, целиком состоящего из нулей,
                с максимальной площадью. */
 
/*............................ЗАГОЛОВОЧНЫЕ ФАЙЛЫ.............................*/
 
#include <stdio.h>
#include <iostream>
using namespace std;
 
/*.........................МОДУЛИ, ДЕФАЙНЫ И ПРОЧЕЕ..........................*/
 
#define WIDTH 10
#define HEIGHT 10
 
/*...............................ТОЧКА ВХОДА.................................*/
 
int main(){
 
    FILE *input=fopen("input.txt","r");    // Открыть файл "input.txt"на чтение.
 
    int x;
 
    int **Mas;
    // Выделение памяти для двумерного массива.
    // Создание массива указателей на строки массива.
    Mas = (int **) malloc(HEIGHT * sizeof(int *));
    // Цикл выделения памяти на каждую строку массива.
    for(x = 0; x < HEIGHT; x++) {
        // Присвоение указателю адреса начала участка памяти, выделенного под строку массива.
        Mas[x] = (int *) malloc(WIDTH * sizeof(int));
    }
 
    int Area=0, MaxArea=0;    // Объявление переменных "Площадь", "Макс. Площадь".
    int CurI, CurJ;
    int Width=0, Height=0;
 
    /* Считываем данные из файла "input.txt" в массив. */
    for(int i=0;i<HEIGHT;i++){
        for(int j=0;j<WIDTH;j++){
            fscanf(input,"%d",&Mas[i][j]);
        }
    }
    /* Находим в массиве прямоугольник из нулей с максимальной площадью. */
    for(int l=0;l<HEIGHT;l++){
        for(int k=0;k<WIDTH;k++){
            
            CurI=l;
            CurJ=k;
            
            while (Mas[CurI][CurJ]==0){
                CurJ++;
                Width++;
            }
            
            CurI=l;
            CurJ=k;
            
            while (Mas[CurI][CurJ]==0){
                CurI++;
                Height++;
            }
            Area=Width*Height;
 
            if(MaxArea<Area)
                MaxArea=Area;
 
            Area=0;
            Width=0;
            Height=0;
        }
    }
    
    cout << "     TA-DA!" << "\n\n";
    cout << "Maximum Area = " << MaxArea << "\n\n";
 
    // Освобождение памяти из-под двумерного массива.
    // Цикл освобождения памяти от каждой строки массива.
    for(x = 0; x < HEIGHT; x++)
    free(Mas[x]);
    // Освобождения памяти из-под массива указателей.
    free(Mas);
    return 0;
}
Что я делаю не так?


Вот матрица:
0 0 0 1 1 0 0 1 1 1
0 0 0 1 1 0 0 1 1 1
0 0 0 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.02.2010, 18:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Максимальная площадь прямоугольника из матрицы. (C++):

Площадь прямоугольника - C++
Написать программу вычисления площади прямоугольника.

Площадь прямоугольника - C++
Возникла проблема с С++. Недавно начал изучать. Такая задача. Найти площадь прямоугольника, задав с клавиатуры значение длинны и ширины. ...

Найти площадь прямоугольника - C++
пожалуйста помогите разобратся в Рекурсии. не могу понять етот код: #include&lt;iostream&gt; #include&lt;conio.h&gt; using namespace std; ...

Вычислить площадь прямоугольника - C++
#include &lt;stdlib.h&gt; #include &lt;iostream&gt; using namespace std; int main() {float a,b, S; cout&lt;&lt;&quot;Input the number of inches\n&quot;; ...

Найти площадь прямоугольника - C++
Известны координаты трех точек A(x1,y1),B(x2,y2),C(x3,y3) , которые являются вершинами некоторого прямоугольника. Найти площадь этого...

Периметр и площадь прямоугольника - C++
Только начали изучать этот язык и не могу понять в чём ошибка.. Задание написать прогу для общёта периметра и площади прямоугольника.. ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
15.02.2010, 18:45 #2
В циклах while надо проверять CurJ и CutI на выход за пределы строки (столбца)
Типа
if (CurJ >= WIDTH) break;
if (CurI >= HEIGTH) break;
Хочется похвалить автора - текст настолько аккуратно оформлен, что просто удовольствие
с ним разбираться
1
DAgot_
22 / 22 / 1
Регистрация: 03.01.2010
Сообщений: 68
15.02.2010, 21:13  [ТС] #3
Спасибо, и за ответ, и за лестные отзывы в сторону оформления кода.
Но оно всё равно не работает:
Тот цикл, в котором растёт CurJ, отрабатывается нормально, а вот с CurI зависает.
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.02.2010, 09:52 #4
DAgot_, У Вас сам алгоритм не правильный.
Вот при таком варианте:
0 0 0 0 0 0 0 1 1 1
0 0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
Ваш алгоритм выдаст заниженный результат, чем есть на самом деле. А при таком варианте
0 0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1
0 1 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 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
/* ГЋГЇГЁГ±Г*Г*ГЁГҐ:    Г„Г*Г*Г*Г*Гї ïðîãðГ*ììГ* ïðåäГ*Г*Г§Г*Г*Г·ГҐГ*Г* äëÿ ïîèñêГ* Гў òåêñòîâîì
                ГґГ*éëå ïðÿìîóãîëüГ*ГЁГЄГ*, öåëèêîì ñîñòîÿùåãî ГЁГ§ Г*óëåé,
                Г± Г¬Г*ГЄГ±ГЁГ¬Г*ëüГ*îé ïëîùГ*äüþ. */
 
/*............................ÇÀÃÎËÎÂÎ×ÍÛÅ ÔÀÉËÛ.............................*/
 
#include <stdio.h>
#include <iostream>
using namespace std;
 
/*.........................ÌÎÄÓËÈ, ÄÅÔÀÉÍÛ È ÏÐÎ×ÅÅ..........................*/
 
#define WIDTH 10
#define HEIGHT 10
 
/*...............................ÒÎ×ÊÀ ÂÕÎÄÀ.................................*/
 
int main(){
 
    FILE *input=fopen("input.txt","r");    // Îòêðûòü ГґГ*éë "input.txt"Г*Г* Г·ГІГҐГ*ГЁГҐ.
 
    int x;
 
    int **Mas;
    // ÂûäåëåГ*ГЁГҐ ГЇГ*ìÿòè äëÿ äâóìåðГ*îãî Г¬Г*Г±Г±ГЁГўГ*.
    // ÑîçäГ*Г*ГЁГҐ Г¬Г*Г±Г±ГЁГўГ* ГіГЄГ*Г§Г*òåëåé Г*Г* ñòðîêè Г¬Г*Г±Г±ГЁГўГ*.
    Mas = (int **) malloc(HEIGHT * sizeof(int *));
    // Г–ГЁГЄГ« âûäåëåГ*ГЁГї ГЇГ*ìÿòè Г*Г* ГЄГ*æäóþ ñòðîêó Г¬Г*Г±Г±ГЁГўГ*.
    for(x = 0; x < HEIGHT; x++) {
        // ÏðèñâîåГ*ГЁГҐ ГіГЄГ*Г§Г*òåëþ Г*äðåñГ* Г*Г*Г·Г*Г«Г* ГіГ·Г*Г±ГІГЄГ* ГЇГ*ìÿòè, âûäåëåГ*Г*îãî ïîä ñòðîêó Г¬Г*Г±Г±ГЁГўГ*.
        Mas[x] = (int *) malloc(WIDTH * sizeof(int));
    }
 
    int Area=0, MaxArea=0;    // ÎáúÿâëåГ*ГЁГҐ ïåðåìåГ*Г*ûõ "ÏëîùГ*äü", "ГЊГ*ГЄГ±. ÏëîùГ*äü".
    int CurI, CurJ;
    int Width=0, Height=0;
 
    /* Ñ÷èòûâГ*ГҐГ¬ Г¤Г*Г*Г*ûå ГЁГ§ ГґГ*éëГ* "input.txt" Гў Г¬Г*Г±Г±ГЁГў. */
    for(int i=0;i<HEIGHT;i++){
        for(int j=0;j<WIDTH;j++){
            fscanf(input,"%d",&Mas[i][j]);
        }
    }
    /* ГЌГ*õîäèì Гў Г¬Г*Г±Г±ГЁГўГҐ ïðÿìîóãîëüГ*ГЁГЄ ГЁГ§ Г*óëåé Г± Г¬Г*ГЄГ±ГЁГ¬Г*ëüГ*îé ïëîùГ*äüþ. */
    for(int l=0;l<HEIGHT;l++){
        for(int k=0;k<WIDTH;k++){
            
            CurI=l;
            CurJ=k;
            int max;
 
            while (CurI<HEIGHT && CurJ<WIDTH && Mas[CurI][CurJ]==0){
                max=0;
                while ( CurI<HEIGHT && CurJ<WIDTH && Mas[CurI][CurJ]==0)
                {
                    CurI++;
                    max++;
                }
                if(CurJ-k==0)
                    Height=max;
                if(max<Height)
                    Height=max;
                Area=(CurJ-k+1)*Height;
                if(MaxArea<Area)
                    MaxArea=Area;
                CurI=l;
                CurJ++;
            }
 
        }
    }
    
    cout << "     TA-DA!" << "\n\n";
    cout << "Maximum Area = " << MaxArea << "\n\n";
 
    // ÎñâîáîæäåГ*ГЁГҐ ГЇГ*ìÿòè ГЁГ§-ïîä äâóìåðГ*îãî Г¬Г*Г±Г±ГЁГўГ*.
    // Г–ГЁГЄГ« îñâîáîæäåГ*ГЁГї ГЇГ*ìÿòè îò ГЄГ*æäîé ñòðîêè Г¬Г*Г±Г±ГЁГўГ*.
    for(x = 0; x < HEIGHT; x++)
    free(Mas[x]);
    // ÎñâîáîæäåГ*ГЁГї ГЇГ*ìÿòè ГЁГ§-ïîä Г¬Г*Г±Г±ГЁГўГ* ГіГЄГ*Г§Г*òåëåé.
    free(Mas);
    return 0;
}
2
DAgot_
22 / 22 / 1
Регистрация: 03.01.2010
Сообщений: 68
16.02.2010, 19:37  [ТС] #5
Алгоритм грубый, согласен, да. Но по условию в матрице именно прямоугольники, поэтому предложенные вами матрицы не попадают под условие задачи.
А так, спасибо Вам огромное.
0
Dashenka
0 / 0 / 0
Регистрация: 04.05.2012
Сообщений: 3
04.05.2012, 20:56 #6
valeriikozlov, почему то ваш алгоритм тоже не работает..(при выполнении программы из матрицы в исходном файле input.txt, он считывает нулевые элементы из первой строки подсчитывает их количество и именно этот результат выдает,а поиск по всем последующим строкам не выполняет..
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.05.2012, 21:28 #7
Цитата Сообщение от Dashenka Посмотреть сообщение
valeriikozlov, почему то ваш алгоритм тоже не работает..(при выполнении программы из матрицы в исходном файле input.txt, он считывает нулевые элементы из первой строки подсчитывает их количество и именно этот результат выдает,а поиск по всем последующим строкам не выполняет..
Dashenka, напишите что у Вас написано в файле input.txt, когда выдает неправильный результат.
0
Dashenka
0 / 0 / 0
Регистрация: 04.05.2012
Сообщений: 3
04.05.2012, 21:38 #8
1 0 0 0 1 0 0 0
1 0 0 1 1 0 0 0
1 0 0 1 1 1 1 1
1 0 0 1 1 1 1 1
1 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1
1 0 0 1 1 1 1 1
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.05.2012, 05:54 #9
Dashenka, нужно быть внимательней. Код, который дан выше работает с матрицами размером 10*10. А Вы пытаетесь вести матрицу размером 8*8, вот и получается неверный ответ.
Для матрицы 8*8 вот это:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
C++
1
2
#define WIDTH 10
#define HEIGHT 10
замените на:
C++
1
2
#define WIDTH 8
#define HEIGHT 8
в последнем коде и получите ответ 10.
1
Dashenka
0 / 0 / 0
Регистрация: 04.05.2012
Сообщений: 3
05.05.2012, 16:20 #10
Спасибо!)))только начинаю программировать в с++)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.05.2012, 16:20
Привет! Вот еще темы с ответами:

Максимальная площадь из введенных треугольников. Не получается добавить функцию в программу - C++
Добрый вечер. Моя программа ищет максимальную площадь из введенных пользователем треугольников (массивы не используются; кол.-во...

Найти периметр и площадь прямоугольника - C++
Класс А позволяет найти периметр прямоугольника по двум сторонам. Класс В, наследник А, имеет метод для определения площади по тем же...

Разработать функцию вычисляющую площадь прямоугольника - C++
Разработать функцию вычисляющую площадь прямоугольника. (для различных встроенных числовых типов.)

Функция вычисляющая периметр и площадь прямоугольника - C++
Ргос5. Описать процедуру RectPS(x1, y1, x2, y2, P, S), которая вычисляет периметр Р и площадь S прямоугольника со сторонами, параллельными...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
05.05.2012, 16:20
Ответ Создать тему
Опции темы

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