Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
Шахром
0 / 0 / 0
Регистрация: 07.01.2018
Сообщений: 13
1

В матрице, состоящей из нулей и единиц найти квадрат наибольшего размера, состоящий целиком из нулей

07.01.2018, 10:27. Просмотров 1043. Ответов 4
Метки нет (Все метки)

В матрице, состоящей из нулей и единиц найти квадрат наибольшего размера, состоящий целиком из нулей.
(Помогите пожалуйста )
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.01.2018, 10:27
Ответы с готовыми решениями:

Найти в матрице квадрат данного размера, состоящий из нулей
В матрице A (m, n), которая состоит из нулей и единиц, найти квадрат данного размера (квадратную...

Найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц. ...

В матрице из нулей и единиц найти квадрат заданного размера, состоящую целиком из нулей
В матрице A (m, n), которая состоит из нулей и единиц, найти квадрат заданного размера (квадратную...

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

Вычислить номер строки матрицы, состоящей из нулей и единиц, с максимальным количеством нулей
Помогите,пожалуйста,написать кусок программы для вычисления номера строки матрицы,состоящей из...

4
Геомеханик
798 / 602 / 939
Регистрация: 26.06.2015
Сообщений: 1,409
07.01.2018, 18:44 2
Лучший ответ Сообщение было отмечено Шахром как решение

Решение

Как понял, так и сделал.
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
#include <stdio.h>
#define N 4
#define M 5
 
inline int array_cmp(const int* a, const int* b, int v){
    while((a < b) && (*a == v))
        ++a;
    return (a == b);
}
 
int main(void){ 
    int i, j, i1, j1, r, n, m, size;
    int mat[N][M] = {
        {1,0,1,0,0},
        {0,0,0,0,1},
        {0,0,0,0,0},
        {1,0,0,0,1}
    };
 
    //поиск max-квадрата в лоб простым перебором
    i1 = N;
    j1 = M;
    for(size = i = 0; i < N; ++i){
        for(j = 0; j < M; ++j){
            if(mat[i][j] != 0)
                continue;
        
            n = i + 2;
            m = j + 2;
            for(; n <= N && m <= M; ++n, ++m){
                for(r = i; r < n; ++r){
                    if(!array_cmp(mat[r] + j, mat[r] + m, 0))
                        break;
                }
 
                if(r == n && (n - i) > size){
                    i1   = i;
                    j1   = j;
                    size = n - i;
                }
            }
        }
    }
 
    //вывод результата
    if(size > 0){
        printf(" row: %d\n col: %d\nsize: %d\n", i1, j1, size);
 
        n = i1 + size;
        m = j1 + size;
        for(i = i1; i < n; ++i){
            for(j = j1; j < m; ++j)
                printf("%d ", mat[i][j]);
            puts("");
        }
    } else      
        puts("No find square!");
    getchar();
    return 0;
}
1
Шахром
0 / 0 / 0
Регистрация: 07.01.2018
Сообщений: 13
11.01.2018, 14:54  [ТС] 3
Спасибо
0
Olej
322 / 170 / 24
Регистрация: 25.03.2012
Сообщений: 712
11.01.2018, 15:54 4
Цитата Сообщение от Геомеханик Посмотреть сообщение
Как понял, так и сделал.
А если у вас матрица а). большая и б). в ней несколько областей, состоящих из 0?
Вы найдёте 1-ю попавшуюся область - локальную.
А вам требуется самая большая (по площади?) из таких областей - глобальный максимум (при чём такие области могут и перекрываться).
0
spvert
217 / 100 / 34
Регистрация: 25.11.2017
Сообщений: 368
Завершенные тесты: 1
11.01.2018, 22:21 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
#define N 10
#define M 6
int matrix[N][M] = {
    { 1,0,1,0,0,0 },
    { 1,0,0,0,0,0 },
    { 1,0,0,0,0,0 },
    { 0,0,0,0,1,1 },
    { 0,0,0,0,0,0 },
    { 0,0,0,0,0,0 },
    { 0,0,0,0,0,0 },
    { 1,0,0,0,0,0 },
    { 0,0,0,0,0,0 },
    { 0,0,0,0,0,0 }
};
int i, j, a, max_size, max_i, max_j;
 
int is_square(int x, int y, int size)
{
    int i1, j1, s = 0;
    for (i1 = x; i1 < x + size; i1++)
    {
        for (j1 = y; j1 < y + size; j1++)
        {
            s += matrix[i1][j1];
        }
    }
    return s;
}
 
int main()
{
    max_size = 0;
    max_i = max_j = 0;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < M; j++)
        {
            if (matrix[i][j] == 0)
            {
                for (a = j; a < M; a++)
                {
                    if (matrix[i][a] != 0) break;
                }
                a -= j; /* max row size */
                if (i + a >= N) a = N - i;
                /* a == max size of square with left upper corner in i,j */
                if (is_square(i, j, a) != 0) continue;
                if (a > max_size)
                {
                    max_size = a;
                    max_i = i;
                    max_j = j;
                }
            }
        }
    }
 
    printf("Max size %d * %d in [%d] [%d]\т", max_size, max_size, max_i, max_j);
    return 0;
}
0
11.01.2018, 22:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.01.2018, 22:21

Составить программу, вычисляющую номера столбца матрицы размера 4x4, состоящей из нулей и единиц
Составить программу, вычисляющую номера столбца матрицы размера 4x4, состоящей из нулей и единиц,...

Найти в матрице, состоящей из нулей и единиц, номера (индексы) хотя бы одной строки и хотя бы одного столбца, не содержащих единицы.
Матрица С(m;m) состоит из нулей и единиц. Найти в ней номера (индексы) хотя бы одной строки и хотя...

Дано матрицу, состоящую из нулей и единиц. Найти самый большой по площади прямоугольник, состоящий из одних единиц
Дано матрицу, состоящую из нулей и единиц. Найти самый большой по площади прямоугольник, состоящий...


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

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

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