FilesExpand file tree

 main

/

MaximumSquareSubmatrix.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

99 lines (73 loc) · 3.24 KB

 main

/

MaximumSquareSubmatrix.java

Copy path

Top

File metadata and controls

• Code
• Blame

99 lines (73 loc) · 3.24 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

/*

(Largest block) Given a square matrix with the elements 0 or 1, write a program

to find a maximum square submatrix whose elements are all 1s. Your program

should prompt the user to enter the number of rows in the matrix. The program

then displays the location of the first element in the maximum square submatrix

and the number of the rows in the submatrix. Here is a sample run

Enter the number of rows in the matrix: 5

Enter the matrix row by row:

1 0 1 0 1 'ENTER'

1 1 1 0 1 'ENTER'

1 0 1 1 1 'ENTER'

1 0 1 1 1 'ENTER'

1 0 1 1 1 'ENTER'

The maximum square submatrix is at (2, 2) with size 3

Your program should implement and use the following method to find the maximum square submatrix:

public static int[] findLargestBlock(int[][] m)

The return value is an array that consists of three values. The first two values are

the row and column indices for the first element in the submatrix, and the thirdimport java.util.Scanner;

*/

import java.util.Scanner;

public class Project8_35{

public static int[] findLargestBlock(int[][] user){

int[] result = new int[3]; //array that holds the result set **int[row index, column index, size]**

int max_size = 0; //initializing length of submatrix box row-wise

for(int i = 0 ; i < user.length; i++){ //traverse through row(i) and column(j) of inputted square matrix

for(int j = 0; j < user[0].length; j++){

if(user[i][j] == 1){

int size = 1; //marker for traversing submatrix

while(i + size < user.length && j + size < user[i].length){ //WHILE LOOP checks is element traversed is 1

boolean isOne = true;

for(int row = i ; row <= i+size; row++){ //traverses the rest of inputted array

for(int column = j ; column <= j+size; column++){

if (user[row][column] == 0){

isOne = false;

break; //breaks while loop if element is 0

}

}

if(!isOne){

break;

}

}

if(isOne){

size++;

} else{

break;

}

}

if(size > max_size){

max_size = size;

result[0] = i; //row index of submatrix

result[1] = j; //column index of submatrix

result[2] = max_size; //size of the submatrix

}

}

}

}

return result;

}

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

System.out.print("Enter the number of rows in the matrix: ");

int rows = input.nextInt();

int[][] matrix = new int[rows][rows];

System.out.println("Enter the matrix row by row:");

for (int i = 0; i < rows; i++) {

for (int j = 0; j < rows; j++) {

matrix[i][j] = input.nextInt();

}

}

int[] result = findLargestBlock(matrix);

System.out.println("The maximum square submatrix is at (" + result[0] + ", " + result[1] + ") with size " + result[2]);

}

}