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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
ulx05
0 / 0 / 0
Регистрация: 17.07.2012
Сообщений: 139
#1

Найти в матрице квадратную подматрицу - C++

01.09.2012, 19:35. Просмотров 1742. Ответов 4
Метки нет (Все метки)

дана матрица а(m,n) из 0 и 1. найти в ней квадратную подматрицу из одних единиц максимального размера.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.09.2012, 19:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти в матрице квадратную подматрицу (C++):

В заданной матрице состоящей из нулей и единиц найти квадратную подматрицу, состоящую целиком из нулей - C++
Черный квадрат. В матрице состоящей из 0 и 1 найти квадрат заданного размера(квадратную подматрицу), состоящий целиком из нулей.

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

Найти в прямоугольной матрице подматрицу из единиц максимального размера. - C++
Прямоуголная подматрица. Вводится матрица a(m,n) из 0 и 1. Найти в ней прямоугольную подматрицу из одних единиц максимального размера (т.е....

Написать юнит-тесты и реализовать следующую функцию: Заполняет квадратную подматрицу заданным числом - C++
Функция самостоятельно контролирует выход подматрицы за пределы массива, т.е. обрезает подматрицу по границам матрицы param matrix -...

Усовершенствовать алгоритм Рабина-Карпа, чтобы он искал символьную подматрицу в символьной матрице - C++
У меня есть этот алгоритм. Кто знает, как усовершенствовать его, чтобы он искал символьную подматрицу m * m в символьной матрицы n * n, при...

Получить квадратную матрицу порядка n — 1 путем отбрасывания в исходной матрице строки и столбца - C++
В данной действительной квадратной матрице порядка n найти наибольший по модулю элемент. Получить квадратную матрицу порядка n — 1 путем...

4
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,284
Записей в блоге: 2
Завершенные тесты: 1
01.09.2012, 19:50 #2
Эта задача интересная) Здесь основная формула - если в позиции a[i][j] стоит 1, то a[i][j] = min (a[i-1][j-1],a[i][j-1],a[i-1][j])+1 Эта формула из динамического программирования. Я точно не помню, как она выводится. После того, как циклы для всех a[i][j] отработают, в массиве a нужно найти максимум - это и будет ответ.
1
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
01.09.2012, 20:12 #3
Попробуйе так:
проверяете все элементы матрицы , если встретится нуль, то вызываете рекурсивно проверку для матрицы размера на 1 меньше , в противном случае возвращаете эту подматрицу.
0
valeriikozlov
Эксперт С++
4672 / 2498 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.09.2012, 02:07 #4
Цитата Сообщение от Dani Посмотреть сообщение
Здесь основная формула - если в позиции a[i][j] стоит 1, то a[i][j] = min (a[i-1][j-1],a[i][j-1],a[i-1][j])+1 Эта формула из динамического программирования.
самый быстрый вариант.
0
zitxbit
88 / 740 / 75
Регистрация: 11.04.2012
Сообщений: 971
02.09.2012, 13:38 #5
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
116
117
118
119
120
121
122
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <memory.h>
 
#define N 20
 
typedef struct Region
{
    int x0;
    int y0;
    int x1;
    int y1;
    int width;
    int height;
} REGION;
 
bool exists(REGION* pRegions, int i, int j)
{
    for (int k = 0; pRegions[k].x0 >= 0; k++)
        if (i >= pRegions[k].y0 && i <= pRegions[k].y1 &&
            j >= pRegions[k].x0 && j <= pRegions[k].x1)
            return true;
 
    return false;
}
 
int main()
{
    int A[N][N] = { { 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
                    { 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1 },
                    { 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1 },
                    { 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1 },
                    { 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1 },
                    { 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
                    { 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0 },
                    { 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0 },
                    { 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0 },
                    { 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0 },
                    { 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0 },
                    { 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                    { 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                    { 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0 },
                    { 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0 },
                    { 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0 },
                    { 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0 },
                    { 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0 },
                    { 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0 },
                    { 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0 } };
 
    REGION* pRegions = new REGION[N * N];
 
    int d = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int pos = j; if (exists(pRegions, i, j)) continue;
            while (A[i][j] == A[i][j+1] && A[i][j] == 1) j++;
 
            bool b = false; int k = i;
            while (k < N && abs(pos-j) > 0 && !b)
            {
                for (int q = pos; q <= j && !b; q++)
                    b = (A[k][q] != A[k+1][q] && A[k+1][q] != 1) ? 1 : 0;
 
                k++;
            }
 
            if (abs(pos-j)+1 > 0 && abs(i-k)-1 > 0)
            {
                pRegions[d].x0 = pos;
                pRegions[d].y0 = i;
                pRegions[d].x1 = j;
                pRegions[d].y1 = k-1;
                pRegions[d].width = abs(pos-j) + 1;
                pRegions[d].height = abs(i-k);
 
                d++;
            }
        }
    }
 
    int max = 0, max_i = 0;
    for (int m = 0; pRegions[m].x0 >= 0; m++)
    {
        printf("x0 = %d y0 = %d x1 = %d y1 = %d width = %d height = %d\n\n",
            pRegions[m].x0, pRegions[m].y0, pRegions[m].x1, 
            pRegions[m].y1, pRegions[m].width, pRegions[m].height);
 
        if (pRegions[m].width * pRegions[m].height > max)
        {
            max = pRegions[m].width * pRegions[m].height;
            max_i = m;
        }
 
        for (int n1 = 0; n1 < pRegions[m].height; n1++)
        {
            for (int n2 = 0; n2 < pRegions[m].width; n2++)
                printf("1 ");
            printf("\n");
        }
 
        printf("\n");
    }
 
    printf("-----------------------------------------------------------\n");
    printf("x0 = %d y0 = %d x1 = %d y1 = %d width = %d height = %d\n\n",
        pRegions[max_i].x0, pRegions[max_i].y0, pRegions[max_i].x1, 
        pRegions[max_i].y1, pRegions[max_i].width, pRegions[max_i].height);
 
    for (int z1 = 0; z1 < pRegions[max_i].height; z1++)
    {
        for (int z2 = 0; z2 < pRegions[max_i].width; z2++)
            printf("1 ");
        printf("\n");
    }
 
    _getch();
 
    return 0;
}
0
Миниатюры
Найти в матрице квадратную подматрицу  
02.09.2012, 13:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.09.2012, 13:38
Привет! Вот еще темы с ответами:

В матрице К размером m*n найти в каждом столбце произведение отрицательных элементов и количество нулевых элементов в матрице - C++
В матрице К размером m*n найти в каждом столбце произведение отрицательных элементов и количество нулевых элементов в матрице. Ребят,...

Найти квадратную матрицу из нулей - C++
На чёрно-белом изображении размером A строк x B столбцов необходимо найти полностью белый квадрат с максимальной площадью. В первой...

Адресация в массиве структур (из матрицы в подматрицу структуры) - C++
Доброго времени суток! Суть вопроса в следующем: Есть матрица А из которой нужно по структурам распихать подматрицы заданной...

Заполнить квадратную матрицу данными из файла и найти столбец с максимальной суммой элементов - C++
Сама суть такова Программно сформировать файл data.txt содержащий 25 случайных чисел, записанных по 5 чисел в строке. Считать этот файл...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

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