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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
DAgot_
 Аватар для DAgot_
22 / 22 / 1
Регистрация: 03.01.2010
Сообщений: 68
15.02.2010, 18:04     Максимальная площадь прямоугольника из матрицы. #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
/* Описание:    Данная программа предназначена для поиска в текстовом
                файле прямоугольника, целиком состоящего из нулей,
                с максимальной площадью. */
 
/*............................ЗАГОЛОВОЧНЫЕ ФАЙЛЫ.............................*/
 
#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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.02.2010, 18:04     Максимальная площадь прямоугольника из матрицы.
Посмотрите здесь:

C++ периметр и площадь прямоугольника
C++ Найти площадь крупнейшего сплошного прямоугольника суши
Площадь прямоугольника C++
Разработать функцию вычисляющую площадь прямоугольника C++
Площадь прямоугольника C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
15.02.2010, 18:45     Максимальная площадь прямоугольника из матрицы. #2
В циклах while надо проверять CurJ и CutI на выход за пределы строки (столбца)
Типа
if (CurJ >= WIDTH) break;
if (CurI >= HEIGTH) break;
Хочется похвалить автора - текст настолько аккуратно оформлен, что просто удовольствие
с ним разбираться
DAgot_
 Аватар для DAgot_
22 / 22 / 1
Регистрация: 03.01.2010
Сообщений: 68
15.02.2010, 21:13  [ТС]     Максимальная площадь прямоугольника из матрицы. #3
Спасибо, и за ответ, и за лестные отзывы в сторону оформления кода.
Но оно всё равно не работает:
Тот цикл, в котором растёт CurJ, отрабатывается нормально, а вот с CurI зависает.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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;
}
DAgot_
 Аватар для DAgot_
22 / 22 / 1
Регистрация: 03.01.2010
Сообщений: 68
16.02.2010, 19:37  [ТС]     Максимальная площадь прямоугольника из матрицы. #5
Алгоритм грубый, согласен, да. Но по условию в матрице именно прямоугольники, поэтому предложенные вами матрицы не попадают под условие задачи.
А так, спасибо Вам огромное.
Dashenka
0 / 0 / 0
Регистрация: 04.05.2012
Сообщений: 3
04.05.2012, 20:56     Максимальная площадь прямоугольника из матрицы. #6
valeriikozlov, почему то ваш алгоритм тоже не работает..(при выполнении программы из матрицы в исходном файле input.txt, он считывает нулевые элементы из первой строки подсчитывает их количество и именно этот результат выдает,а поиск по всем последующим строкам не выполняет..
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.05.2012, 21:28     Максимальная площадь прямоугольника из матрицы. #7
Цитата Сообщение от Dashenka Посмотреть сообщение
valeriikozlov, почему то ваш алгоритм тоже не работает..(при выполнении программы из матрицы в исходном файле input.txt, он считывает нулевые элементы из первой строки подсчитывает их количество и именно этот результат выдает,а поиск по всем последующим строкам не выполняет..
Dashenka, напишите что у Вас написано в файле input.txt, когда выдает неправильный результат.
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
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.05.2012, 16:20     Максимальная площадь прямоугольника из матрицы.
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Dashenka
0 / 0 / 0
Регистрация: 04.05.2012
Сообщений: 3
05.05.2012, 16:20     Максимальная площадь прямоугольника из матрицы. #10
Спасибо!)))только начинаю программировать в с++)
Yandex
Объявления
05.05.2012, 16:20     Максимальная площадь прямоугольника из матрицы.
Ответ Создать тему
Опции темы

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