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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
ulx05
0 / 0 / 0
Регистрация: 17.07.2012
Сообщений: 139
01.09.2012, 19:35     Найти в матрице квадратную подматрицу #1
дана матрица а(m,n) из 0 и 1. найти в ней квадратную подматрицу из одних единиц максимального размера.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.09.2012, 19:35     Найти в матрице квадратную подматрицу
Посмотрите здесь:

3. Найти в матрице первую строку C++
C++ Найти квадратную подматрицу максимального размера
Найти в прямоугольной матрице подматрицу из единиц максимального размера. C++
C++ Найти квадратную матрицу из нулей
C++ В матрице А (mxn) найти найти сумму элементов по колонкам, значения которых по модулю меньше заданного числа К
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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 нужно найти максимум - это и будет ответ.
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
01.09.2012, 20:12     Найти в матрице квадратную подматрицу #3
Попробуйе так:
проверяете все элементы матрицы , если встретится нуль, то вызываете рекурсивно проверку для матрицы размера на 1 меньше , в противном случае возвращаете эту подматрицу.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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 Эта формула из динамического программирования.
самый быстрый вариант.
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 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;
}
Миниатюры
Найти в матрице квадратную подматрицу  
Yandex
Объявления
02.09.2012, 13:38     Найти в матрице квадратную подматрицу
Ответ Создать тему
Опции темы

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