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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Каков тип строковых литералов? http://www.cyberforum.ru/cpp-beginners/thread1508545.html
Каков тип rvalue строки "Hello"? const char* const или const char* ? const char* some1 = "Hello";
C++ Как перевести строку в BSTR* Как перевести обычную строку в BSTR* ??? http://www.cyberforum.ru/cpp-beginners/thread1508535.html
C++ Посоветуйте модульные подходы создания класса
Добрый вечер, пишу Tower Defence - хочу уйти от длинных классов и попробывать в этот раз какуе-то модульную систему сбора логики. Собираюсь использовать PIML и интерфейсы и friend class фабрику, собирать класс как-то так: class IEnemyTargetSelect { // потомки описывают поведения выбора врага: ближайщих, максимальное количество повреждения, добивания };
Перегрузка операции >> C++
Здравствуйте. Возник такой вопрос: возможни ли перегрузить оператор >> так, чтобы пользователь мог вводить с клавиатуры время в формату хх:уу (пример 12:35). Проблема в том, что не знаю как сделать так, чтобы программа воспринимала символ ":" как разделитель между часами и минутами.
C++ Вычислить среднеквадратичное отклонение http://www.cyberforum.ru/cpp-beginners/thread1508465.html
Написать программу , которая будет выполнять вычисления отклонения от ср. арифм. (число - ср. арифм.).
C++ Как в С++ подключить API ВКонтакте? Приветствую уважаемые посетители cyberforum! Хотелось бы узнать как в С++ подключить API ВКонтакта? подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2801 / 1577 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
02.08.2015, 19:23     Найти максимальную площадь квадратной подматрицы, состоящей только из 1
Цитата Сообщение от 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
}
 
Текущее время: 20:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru