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

Найти максимальную площадь квадратной подматрицы, состоящей только из 1 - C++

Восстановить пароль Регистрация
 
qeque
0 / 0 / 0
Регистрация: 02.08.2015
Сообщений: 1
02.08.2015, 09:28     Найти максимальную площадь квадратной подматрицы, состоящей только из 1 #1
Дана матрица NxN, заполненная 0 и 1. Найти максимальную площадь квадратной подматрицы, состоящей из 1.
Нашел в сети алгоритм решения, но чтобы совсем уж нагло не списывать, проверяю матрицу в один проход и слева направо, сверху вниз. Написал решение, вроде компилится нормально, но падает при запуске ехе. CodeBlocks 13.12
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;
main(){
    int n,i,j,a[1000][1000],m=0;
    cin>>n;
    for (i=0;i<n;i++){
        for (j=0;j<n;j++){
            cin>>a[i][j];
            if (i==0||j==0) continue; else 
            a[i][j]=min(min(a[i][j-1],a[i-1][j]),a[i-1][j-1])+1;
            if (a[i][j]>m) m=a[i][j];
        }
    }
    cout<<m*m;
}
Добавлено через 13 минут
Понял в чем проблема, падает из-за матрицы 1000х1000. Буду пробовать с векторами
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.08.2015, 09:28     Найти максимальную площадь квадратной подматрицы, состоящей только из 1
Посмотрите здесь:

найти площадь грани, площадь полной поверхности и объем этого куба. C++
C++ Составить программу для подсчета суммы положительных элементов квадратной таблицы В, состоящей из N × N целых чисел
Найти максимальную оценку студента и вывести его ID потом фамилию и максимальную оценку C++
В строке, состоящей из слов и знаков препинания найти все слова-палиндромы C++
C++ Подпрограммы в С++11. Площадь "елки", состоящей из четырех треугольников
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MansMI
1047 / 844 / 205
Регистрация: 08.01.2012
Сообщений: 3,026
02.08.2015, 09:42     Найти максимальную площадь квадратной подматрицы, состоящей только из 1 #2
массив на сhar измените, странный алгоритм, массив вроде вручную забивается, а потом ячейка пересчитывается, так юзер свою матрицу и не узнает
zss
Модератор
Эксперт С++
 Аватар для zss
5946 / 5551 / 1784
Регистрация: 18.12.2011
Сообщений: 14,178
Завершенные тесты: 1
02.08.2015, 10:20     Найти максимальную площадь квадратной подматрицы, состоящей только из 1 #3
Сделайте массив глобальным, он в стек не помещается.
Правда я не понимаю, как вручную можно ввести миллион элементов.
А в принципе, надо использовать динамическое выделение памяти.
См. Образцы (шаблоны) программ для типовых задач

И еще, результат будет неправильный при вводе отрицательных чисел. m надо присвоить значение первого введенного числа.
C++
1
2
3
cin>>a[i][j];
if(i==0 && j==0)
   m=a[0][0];
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
02.08.2015, 19:23     Найти максимальную площадь квадратной подматрицы, состоящей только из 1 #4
Цитата Сообщение от qeque Посмотреть сообщение
Буду пробовать с векторами
Мэпы удобнее.
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
/////////////////////////////////////////////////////////////////////////////////////////
//Дана матрица NxN, заполненная 0 и 1. Найти максимальную площадь квадратной подматрицы, состоящей из 1.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <unordered_map>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::unordered_map    < int,  int     >   T_row;
typedef std::unordered_map    < int,  T_row   >   T_matr;
/////////////////////////////////////////////////////////////////////////////////////////
void    for_dim_set_rand_matr
    (
        int         matr_dim,
        T_matr  &   matr
    )
{
    auto    param   =   rand() % 100 + 1;
 
    for( int  i = 0; i < matr_dim; ++i )
    {
        for( int  j = 0; j < matr_dim; ++j )
        {
            matr[i][j]  =   rand() % param  !=  0;
        }
    }//for
}
/////////////////////////////////////////////////////////////////////////////////////////
void    print_matr( T_matr  &   matr )
{
    int     matr_dim    =   matr.size();
 
    for( int  i = 0; i < matr_dim; ++i )
    {
        for( int  j = 0; j < matr_dim; ++j )
        {
            std::cout   <<  matr[i][j]
                        <<  ' ';
        }//for
 
        std::cout   <<  std::endl;
    }//for
}
/////////////////////////////////////////////////////////////////////////////////////////
int     get_area_of_square_submatrix( T_matr    &   matr )
{
    int     dim_res     =   0;
    int     matr_dim    =   matr.size();
 
    for( int  i = 1; i < matr_dim; ++i )
    {
        for( int  j = 1; j < matr_dim; ++j )
        {
            auto    &   elem_cur    =   matr[i][j];
 
            if( !elem_cur )
            {
                continue;
            }
 
            elem_cur    =       std::min
                                    (
                                        std::min
                                            (
                                                matr    [ i - 1 ]   [ j     ],
                                                matr    [ i     ]   [ j - 1 ]
                                            ),
 
                                        matr            [ i - 1 ]   [ j - 1 ]
                                    )
 
                            +   1;
 
            dim_res     =   std::max    (
                                            dim_res,
                                            elem_cur
                                        );
        }//for
    }//for
 
    return      dim_res
            *   dim_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    static  const   int     MATR_DIM    =   10;
    srand(unsigned(time(0)));
    T_matr  matr;
 
    for(;;)
    {
        for_dim_set_rand_matr
            (
                MATR_DIM,
                matr
            );
 
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
 
        print_matr( matr );
 
        std::cout   <<  std::endl
                    <<  "s = "
                    <<  get_area_of_square_submatrix( matr )
                    <<  std::endl;
 
        print_matr( matr );
        system("pause");
    }//for
}
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,333
Завершенные тесты: 1
03.08.2015, 11:28     Найти максимальную площадь квадратной подматрицы, состоящей только из 1 #5
Цитата Сообщение от qeque Посмотреть сообщение
Дана матрица NxN, заполненная 0 и 1. Найти максимальную площадь квадратной подматрицы, состоящей из 1.
Я вот в этой теме детально рассматривал: Найти площадь крупнейшего сплошного прямоугольника суши
Yandex
Объявления
03.08.2015, 11:28     Найти максимальную площадь квадратной подматрицы, состоящей только из 1
Ответ Создать тему
Опции темы

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