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

Узнай цену своей работы

Формулировка задачи:

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

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

textual
Листинг программы
#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. Объявлены переменные:
    • i, j, i1, j1, r, n, m, size (для основной работы)
    • N, M (для определения размеров матрицы)
    • mat[N][M] (для хранения матрицы)
  2. Заполнение матрицы значениями:
    • В ячейках матрицы mat[i][j] со значением 1 стоят единицы, со значением 0 - нули.
  3. Поиск максимального квадрата, состоящего из нулей:
    • Простым перебором итераций по всем элементам матрицы.
    • Если элемент матрицы равен нулю, то его можно использовать для образования нового квадрата.
    • Поиск начинается с элемента матрицы, находящегося в правом нижнем углу.
    • Если найденный квадрат больше текущего максимального, то обновляются его координаты и размер.
    • Если после прохода по всем элементам матрицы максимальный квадрат не найден, выводится сообщение No find square!.
  4. Вывод результата:
    • Если максимальный квадрат найден, то выводятся его координаты и размер.
    • Затем выводится сам квадрат, заполненный нулями.
  5. Ввод-вывод:
    • Ввод осуществляется с помощью функции getchar() в конце программы.
    • Вывод осуществляется с помощью функций printf() и puts().

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

8   голосов , оценка 4.125 из 5
Похожие ответы