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