***8.35（最大块）给定一个元素为0或者1的方阵，编写程序，找到一个元素都为1的最大的子方阵。程序提示用户输入矩阵的行数。然后显示最大的子方阵的第一个元素、行数

• 题目
• • 题目描述与运行示例
  • 破题
• 代码（非正式）
• 正式代码与博主错误

题目

题目描述与运行示例

***8.35（最大块）给定一个元素为0或者1的方阵，编写程序，找到一个元素都为1的最大的子方阵。程序提示用户输入矩阵的行数。然后显示最大的子方阵的第一个元素、最大子方阵的行数

Enter the number of rows in the matrix: 5
Enter the matrix row by row: 
1 0 1 0 1
1 1 1 0 1
1 0 1 1 1
1 0 1 1 1
1 0 1 1 1
The maximum square submatrix is at (2, 2) with size 3

破题

1. 输出提示语句，从控制台获取方阵大小
2. 声明一个二维数组，长度为刚刚获取的大小
3. 使用循环获取用户赋值
4. 使用多层循环遍历数组，找到最大的子方阵
5. 输出子方阵第一个元素位置和行数

代码（非正式）

import java.util.Scanner;public class Test8_35 {public static void main(String[] args) {//1. 输出提示语句，从控制台获取方阵大小Scanner input = new Scanner(System.in);System.out.print("Enter the number of rows in the matrix: ");int length = input.nextInt();//2. 声明一个二维数组，长度为刚刚获取的大小int[][] arr = new int[length][length];//3. 使用循环获取用户赋值System.out.println("Enter the matrix row by row: ");for (int i = 0 ; i < length ; i++){for (int j = 0 ; j < length ; j++){arr[i][j] = input.nextInt();}}//4. 使用多层循环遍历数组，找到最大的子方阵// 子方阵长度从arr.length开始到1结束，全为1的则输出结果for (int substring_length = length ; substring_length > 0 ; substring_length--){for (int i = 0 ; i <= length - substring_length ; i++){for (int j = 0 ; j <= length - substring_length ; j++){if (is_substring(arr, i, j, substring_length)){System.out.println("The maximum square submatrix is at (" + i +", " + j + ") with size " + substring_length);return;}}}}}/** 判断下标从[i][j]开始的substring_length围成的矩阵中是否全部为1 */public static boolean is_substring(int[][] arr, int i, int j, int length){for (int x = i ; x < i + length ; x++){for (int y = j ; y < j + length ; y++){if (arr[x][y] != 1){return false;}}}return true;}
}

正式代码与博主错误

做题的时候没看到最后还有一行要求
程序需要实现和使用下面的方法来找到最大的子方阵
public static int[] findLargestBlock(int[][] m)
返回值是一个包含三个值的数组
前面两个值是子方阵的行和列的下标，第三个值是子方阵中的行数

对程序修改如下：

import java.util.Scanner;public class Test8_35 {public static void main(String[] args) {//1. 输出提示语句，从控制台获取方阵大小Scanner input = new Scanner(System.in);System.out.print("Enter the number of rows in the matrix: ");int length = input.nextInt();//2. 声明一个二维数组，长度为刚刚获取的大小int[][] arr = new int[length][length];//3. 使用循环获取用户赋值System.out.println("Enter the matrix row by row: ");for (int i = 0; i < length; i++) {for (int j = 0; j < length; j++) {arr[i][j] = input.nextInt();}}//4. 传入方法int[] feedback = findLargestBlock(arr);// 输出System.out.println("The maximum square submatrix is at (" + feedback[0] +", " + feedback[1] + ") with size " + feedback[2]);}public static int[] findLargestBlock(int[][] m){int[] feedback = new int[3];for (int substring_length = m.length ; substring_length > 0 ; substring_length--){for (int i = 0 ; i <= m.length - substring_length ; i++){for (int j = 0 ; j <= m.length - substring_length ; j++){if (is_substring(m, i, j, substring_length)){feedback[0] = i;feedback[1] = j;feedback[2] = substring_length;return feedback;}}}}return feedback;}/** 判断下标从[i][j]开始的substring_length围成的矩阵中是否全部为1 */public static boolean is_substring(int[][] arr, int i, int j, int length){for (int x = i ; x < i + length ; x++){for (int y = j ; y < j + length ; y++){if (arr[x][y] != 1){return false;}}}return true;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！