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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ std::string Трим http://www.cyberforum.ru/cpp-beginners/thread95873.html
Как сделать трим (вырезание из начала\конца строки лишних символов таких как пробелы, табуляции...) в std::string? Я недавно нашёл у себя в коде такое: void LTrim(std::string* String, const char* Trim) { int i = 0; while ( Trim ) { // Если текущий символ - трим-символ if ( (*String) == Trim ) { //удаляем его и начинаем проверку заново
C++ Есть ли такие утилиты. Я ищу утилиты которые позволяют находить утечки памяти... У меня возник вопрос есть ли программные утилиты(подобного рода), которые подключаются к VC++ 6.0. или VS 2008. Если такие утилиты существуют поставьте ссылку на ресурс от куда можно взять хотя бы одну такую утилиту. please... http://www.cyberforum.ru/cpp-beginners/thread95852.html
С++ Win32 API C++
Подскажите книгу с самым доступным объяснением по данной теме. Что-то в роде "С++ за 21 день" только по Win32. Для чайников так сказать... :) Заранее спасибо.
Подскажите книжку C++
Привет всем..Я в C++ новичёк... но я хорошо соображаю и очень хочу научится.У меня есть Книга "С++ для чайников" но в ней нет задач чтобы программировать и там много написано непонятно и я кое где не понимаю... Пожалуйста подскажите мне Книжку написанную удобно и понятно с задачами на каждую тему..(Желательно книжку которая помогла вам подняться с нулевого уровня) P.S. Я думаю такие темы уже...
C++ вопрос по структурам http://www.cyberforum.ru/cpp-beginners/thread95836.html
Я начал писать программу на следующию задачу Описать структуру с именем STUDENT, содержащую следующие поля: -Фамилия и инициалы -Номер группы -Успеваемость(массив из 5ти элементов). Написать программу выполняющую следующие действия: -Ввод с клавиатуры данных в массив, состоящий из 10ти структур типа STUDENT:записи должны быть упорядочены по возрастанию среднего балла; -Вывод на дисплей...
C++ Проход по квадрату Вот такая задачка! Помогите чем можете!!!!!! Пройдите в квадрате от клеточки 1 к клеточке 2 так, чтобы посетить все клеточки по одному разу, не попадая в черных. подробнее

Показать сообщение отдельно
DAgot_
 Аватар для DAgot_
22 / 22 / 1
Регистрация: 03.01.2010
Сообщений: 68

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

15.02.2010, 18:04. Просмотров 1616. Ответов 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
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 07:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru