Упражнения C: Найти максимальный размер квадратной подматрицы со всеми 1

C Массив: Упражнение-89 с раствором

Напишите программу на C, чтобы найти квадратную подматрицу максимального размера со всеми единицами.

Пример решения:

Код C:

// C/C++ code for Maximum size square sub-matrix with all 1s 
#include<stdio.h> 
#define bool int 
#define row 6 
#define col 5 
  
void squreSubarrayOfOnes (bool arr1[row][col]) 
{ 
  int i,j; 
  int sub_arr[row][col]; 
  int max_s, mx_i, mx_j;  
   
  for(i = 0; i < row; i++) 
     sub_arr[i][0] = arr1[i][0]; 
   
  for(j = 0; j < col; j++) 
     sub_arr[0][j] = arr1[0][j]; 
       
  for(i = 1; i < row; i++) 
  { 
    for(j = 1; j < col; j++) 
    { 
      if(arr1[i][j] == 1)  
        sub_arr[i][j] = min(sub_arr[i][j-1], sub_arr[i-1][j], sub_arr[i-1][j-1]) + 1; 
      else
        sub_arr[i][j] = 0; 
    }     
  }  
    
  max_s = sub_arr[0][0]; mx_i = 0; mx_j = 0; 
  for(i = 0; i < row; i++) 
  { 
    for(j = 0; j < col; j++) 
    { 
      if(max_s < sub_arr[i][j]) 
      { 
         max_s = sub_arr[i][j]; 
         mx_i = i;  
         mx_j = j; 
      }         
    }                  
  }      
    
  printf("The maximum size sub-matrix is: \n"); 
  for(i = mx_i; i > mx_i - max_s; i--) 
  { 
    for(j = mx_j; j > mx_j - max_s; j--) 
    { 
      printf("%d ", arr1[i][j]); 
    }   
    printf("\n"); 
  }   
}      
  
int min(int a, int b, int c) 
{ 
  int m = a; 
  if (m > b)  
    m = b; 
  if (m > c)  
    m = c; 
  return m; 
} 
  
int main() 
{ 
  bool arr1[row][col] =  {{0, 1, 0, 1, 1},  
                   {1, 1, 1, 1, 0},  
                   {1, 1, 1, 1, 0}, 
                   {1, 1, 1, 1, 0}, 
                   {1, 1, 1, 1, 1}, 
                   {0, 1, 0, 1, 0}}; 
        int i,j;                   
 //------------- print original array ------------------	
	printf("The given array in matrix form is :  \n");
	for(i = 0; i < row; i++)
	{
	for (j=0;j<col;j++)
	{
	printf("%d  ", arr1[i][j]);
    } 
	printf("\n");
	}
//------------------------------------------------------ 				   
                 
  squreSubarrayOfOnes(arr1); 
}

Пример вывода:

 Данный массив в матричной форме:  
0 1 0 1 1  
1 1 1 1 0  
1 1 1 1 0  
1 1 1 1 0  
1 1 1 1 1  
0 1 0 1 0  
Максимальный размер подматрицы: 
1 1 1 1 
1 1 1 1 
1 1 1 1 
1 1 1 1 

Блок - схема:

Редактор кода программирования C:

Улучшите этот пример решения и опубликуйте свой код через Disqus.

Предыдущий: Напишите программу на C, чтобы найти максимум n - m
Далее: задан массив размером n такой, что каждый элемент находится в диапазоне от 0 до n-1. Напишите программу на C, чтобы переставить данный массив так, чтобы arr [i] стал arr [arr [i]].