write a java program for the following question: Given a square matrix with the
ID: 3588505 • Letter: W
Question
write a java program for the following question:
Given a square matrix with the elements 0 and 1, write a program to find a maximum square submatrix whose elements are all 1s. The program first prompts the user to enter the number of rows in the matrix and then the rows, one by one. The output produced by the program consists of the location of the first element in the maximum square submatrix (the left top corner element in the printed matrix) plus the number of rows in that submatrix. Sample run: Enter the number of rows in the matrix: 5 Enter the matrix row by row: 1 1 1 0 1 0011 1 1 01 1 1 0 1 1 1 1 The maximum square submatrix is at (2,2) with size 3. You don't have to consider input exceptionsExplanation / Answer
// JAVA Code for maxSubSquareMatrix with all 1s
import java.util.Scanner;
public class SubSquareMatrix
{
// method for maxSubSquareMatrix with all 1s
static void maxSubSquareMatrix(int M[][])
{
int i,j;
int R = M.length; //no of rows in M[][]
int C = M[0].length; //no of columns in M[][]
int S[][] = new int[R][C];
int max_of_s, max_i, max_j;
/* Set first column of S[][]*/
for(i = 0; i < R; i++)
S[i][0] = M[i][0];
/* Set first row of S[][]*/
for(j = 0; j < C; j++)
S[0][j] = M[0][j];
/* Construct other entries of S[][]*/
for(i = 1; i < R; i++)
{
for(j = 1; j < C; j++)
{
if(M[i][j] == 1)
S[i][j] = Math.min(S[i][j-1],Math.min(S[i-1][j], S[i-1][j-1])) + 1;
else
S[i][j] = 0;
}
}
/* Find the maximum entry, and indexes of maximum entry
in S[][] */
max_of_s = S[0][0]; max_i = 0; max_j = 0;
for(i = 0; i < R; i++)
{
for(j = 0; j < C; j++)
{
if(max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}
int rstart=max_i - max_of_s+1;
int cstart=max_j - max_of_s+1;
int rsize=max_i - rstart+1;
System.out.println("The Maximum square submatrix is at ("+rstart+","+cstart+")with size "+rsize);
System.out.println("Maximum size sub-matrix is: ");
for(i = max_i; i > max_i - max_of_s; i--)
{
for(j = max_j; j > max_j - max_of_s; j--)
{
System.out.print(M[i][j] + " ");
}
System.out.println();
}
}
// Driver program
public static void main(String[] args)
{
int row, col, i, j;
/* int Matrix[][] = {{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0}}; */
int Matrix[][] = new int[100][100];
Scanner scan = new Scanner(System.in);
System.out.println("Enter Number of Row for Array : ");
row = scan.nextInt();
System.out.println("Enter Number of Column for Array : ");
col = scan.nextInt();
System.out.println("Enter " +(row*col)+ " Array Elements : ");
for(i=0; i<row; i++)
{
for(j=0; j<col; j++)
{
Matrix[i][j] = scan.nextInt();
}
}
maxSubSquareMatrix(Matrix);
}
}
Output :
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.