Функция получающая как параметер Матрицу целых чисел NxN и количество ее строк - C (СИ)
Формулировка задачи:
Доброго времени суток друзья, вопрос такой.
мне надо написать функцию получающую матрицу NxN и количество ее строк(количество строк ровно количеству столбиков).
функция выдает на экране данные( первый индекс, количество строк и число данных) квадратной максимальной под-матрицы в которой только нули.
пример: матрица 5x5
0 0 0 0 0
0 0 0 0 0
1 1 0 0 0
1 1 0 0 0
1 1 1 1 1
вывод на экран:
Max zero matrix: Start[0,2], Size=3, Zeros=9.
заранее спасибо.
Решение задачи: «Функция получающая как параметер Матрицу целых чисел NxN и количество ее строк»
textual
Листинг программы
#include <stdio.h>
#define N 5
typedef struct {
int row, col, size;
} mres;
static int is_cmp(int m[][N], int i0, int j0, int i1, int j1);
int mfind_sub(int m[][N], mres* r);
int main(void){
int i, j;
mres r;
int m[N][N] = {
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 1, 1, 0, 0, 0 },
{ 1, 1, 0, 0, 0 },
{ 1, 1, 1, 1, 1 }
};
if(mfind_sub(m, &r)){
printf("Max zero matrix: Start[%d, %d], Size=%d, Zeros=%d.\n",
r.row, r.col, r.size, r.size * r.size);
// для результата поиска вывести наглядный результат
for(i = r.row; i < r.row + r.size; ++i){
for(j = r.col; j < r.col + r.size; ++j)
m[i][j] = 8;
}
for(i = 0; i < N; ++i){
for(j = 0; j < N; ++j)
putchar(m[i][j] + '0');
putchar('\n');
}
} else
puts("error find!");
return 0;
}
int mfind_sub(int m[][N], mres* r){
int i, j, i1, j1, a, b, n;
r->size = r->col = r->row = 0;
for(i = 0; i < N; ++i){
for(j = 0; j < N; ++j){
if(m[i][j] != 0)
continue;
i1 = i;
while((i1 < N) && (m[i1][j] == 0))
++i1;
if((a = (i1 - i)) <= 1)
continue;
j1 = j;
while((j1 < N) && (m[i][j1] == 0))
++j1;
if((b = (j1 - j)) <= 1)
continue;
n = (a < b) ? a : b;
if(n <= 1)
continue;
for(; n > 1; --n, --i1, --j1){
if(is_cmp(m, i, j, i1, j1)){
if(n > r->size){
r->size = n;
r->col = j;
r->row = i;
}
break;
}
}
if(r->size == N){
i = N;
break;
}
}
}
return (r->size > 0);
}
static int is_cmp(int m[][N], int i0, int j0, int i1, int j1){
int i, j;
for(i = i0; i < i1; ++i){
for(j = j0; j < j1; ++j){
if(m[i][j] != 0)
return 0;
}
}
return 1;
}