1 / 1 / 1
Регистрация: 17.07.2012
Сообщений: 139
1

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

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

дана матрица а(m,n) из 0 и 1. найти в ней квадратную подматрицу из одних единиц максимального размера.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.09.2012, 19:35
Ответы с готовыми решениями:

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

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

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

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

4
1404 / 646 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
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
12 / 12 / 3
Регистрация: 27.07.2012
Сообщений: 208
01.09.2012, 20:12 3
Попробуйе так:
проверяете все элементы матрицы , если встретится нуль, то вызываете рекурсивно проверку для матрицы размера на 1 меньше , в противном случае возвращаете эту подматрицу.
0
Эксперт С++
4722 / 2543 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
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
96 / 748 / 279
Регистрация: 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.09.2012, 13:38
Помогаю со студенческими работами здесь

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

Найти нулевую подматрицу максимального размера
Здравствуйте, уважаемые пользователи! Перед мной встала задача нахождения нулевой подматрицы...

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru