【蓝桥杯】边界为1的最大子方阵的优化

优化方法:

直接判断某个顶点是否为矩阵的左上角。通过辅助数组。该数组负责记录该顶点(包含自身)的右方,和下方1的个数。可以看作是改二维数组中又包含一个二元组。

1 1 1 0
1 1 0 1
1 1 0 1
0 1 1 1

其辅助数组为(右,下)

(3,1) (4,1) (1,1) (0,0)
(2,2) (1,3) (0,0) (1,3)
(2,1) (1,2) (0,0) (1,2)
(0,0) (3,1) (2,1) (1,1)

加了底纹的部分,(2,2)表示包括自身在内右边又2个1,向下有2个1。所以正方形的上边和左边已证明可以构成边框全为1;

        (2,1)2表示向右有2个1,构成正方形的下边;(1,3)3表示向下有3个1,构成正方形的右边。所以边框全是1的最大正方形的边长长度为2。

满足这四个部分,就证明可以构成边界全为1的最大正方形。

该部分就是替换上一篇中的内层while的思路。

难点在于辅助数组generateHelpRec的建立。

  1.格式为(右,下),所以建立会从右下角开始,一行一行的向上走;

  2.可以先初始化最后一行,需要注意的就是数组下标不要越界;

代码如下:

  1 public class case4_1 {
  2 
  3     public static void main(String[] args) {
  4         /*    int arr[][] = { 
  5         { 1, 1, 1,1}, 
  6         { 1, 0, 1,1}, 
  7         { 1, 1, 1,1}, 
  8         { 1, 0, 1,0}, 
  9         };
 10         */
 11         int arr[][] = { 
 12             { 1, 0, 1, 1,1 }, 
 13             { 1, 1, 1, 1,1 }, 
 14             { 1, 1, 1, 0,1 }, 
 15             { 1, 1, 1, 1,1 }, 
 16             { 1, 1, 1, 1,1 }, 
 17             };
 18         generateHelpRec(arr, arr.length);
 19        // printArr(rec, arr.length);//该方法主要是为了检测三维数组创建的是否正确。
 20         int res = max(arr, arr.length);
 21         System.out.println(res);
 22 
 23     }
 24 
 25     private static void printArr(int[][][] rec2, int N) {
 26         for (int i = 0; i < N; i++) {
 27             for (int j = 0; j < N; j++) {
 28                 System.out.print("(" + rec[i][j][0] + "," + rec[i][j][1] + ")"
 29                         + "\t");
 30             }
 31             System.out.println();
 32         }
 33     }
 34 
 35     static int[][][] rec;
 36 
 37     // 创建辅助表;三维数组
 38     private static void generateHelpRec(int[][] arr, int N) {
 39         rec = new int[N][N][2];
 40         // 先初始化最后一行;
 41         int row = N - 1;
 42         for (int j = N - 1; j >= 0; j--) {
 43             int value = arr[row][j];
 44             if (value == 1) {
 45                 if (j == N - 1)// 右边1的个数,j增加
 46                     rec[row][j][0] = 1;
 47                 else
 48                     rec[row][j][0] = rec[row][j + 1][0] + 1;
 49 
 50                 rec[row][j][1] = 1;
 51             }
 52 
 53         }
 54         row--;
 55         // 构建三维表
 56         for (int i = row; i >= 0; i--) {
 57             for (int j = N - 1; j >= 0; j--) {
 58                 int value = arr[i][j];
 59                 if (value == 1) {
 60                     if (j == N - 1) {
 61                         rec[i][j][0] = 1;
 62                     } else {
 63                         rec[i][j][0] = rec[i][j + 1][0] + 1;
 64                     }
 65                     rec[i][j][1] = rec[i + 1][j][1] + 1;
 66                 }
 67             }
 68         }
 69 
 70     }
 71 
 72     static int max(int[][] matrix, int N) {
 73         int n = N;
 74         while (n > 0) {
 75             for (int i = 0; i < N; i++) {
 76                 if (i + n > N)
 77                     break;
 78                 l3: for (int j = 0; j < N; j++) {
 79                     if (j + n > N)
 80                         break;
 81 
 82                     if (check(i, j, n) == true)
 83                         return n;
 84 
 85                 }
 86             }
 87 
 88             n--;
 89 
 90         }
 91 
 92         return 0;
 93     }
 94 
 95     private static boolean check(int i, int j, int n) {
 96         if (rec[i][j][0] >= n && rec[i][j][1] >= n && rec[i + n - 1][j][0] >= n
 97                 && rec[i][j + n - 1][1] >= n)
 98             return true;
 99         return false;
100     }
101 }

 上述代码输出 :4

欢迎大家一起来交流。

上一篇:luogu P2241 统计方形(数据加强版)


下一篇:2018数学建模国赛B题 --python实现情况1