边界都是1的最大正方形大小

灰太狼 2022-05-29 05:38 166阅读 0赞

![Center][]

//边界都是1的最大正方形大小
    public class MaxMatrixSize{
    	
    
    	//返回边框大小全是1的最大长度
    	public static int GetMaxMatrixSize(int[][]matrix)
    	{
              int max=0;
              if(matrix==null||matrix.length==0)
              {
              	return -1;
              }
              int topr=0;
              int topc=0;
              int downr=matrix.length-1;
              int downc=matrix[0].length-1; 
                         
              max=IsMatrix(matrix,topr,topc,downr,downc);
              //System.out.println(topr+""+topc+""+downr+""+downc);
              int max1=0;
              int max2=0;
              int max3=0;
              if(max==0)
              {
              	max1=IsMatrix(matrix,topr,++topc,--downr,downc); //左移
              	--topc;
              	++downr;
              	max2=IsMatrix(matrix,++topr,topc,downr,--downc); //下移
              	--topr;
              	++downc;
              	max3=IsMatrix(matrix,++topr,++topc,--downr,--downc); //对角线移动
              	max=Math.max(max1,max2);
                max=Math.max(max,max3);
              }
    
              return max; 
    	}
        //判断是否满足要求的矩阵
    	public static int IsMatrix(int[][]matrix,int topr,int topc,int downr,int downc)
    	{
    		 int max=0;
    		 int sumr=0;
             int sumc=0;
    		 //扫描左上角行
              for(int i=topc;i<=downc;i++)
              {
                       sumr+=matrix[topr][i];
              	  
              }
              //扫描左上角列
              for(int i=topr;i<=downr;i++)
              {
                       sumc+=matrix[i][topc];
              }
           
              int dsumr=0;
              int dsumc=0;
              //扫描右下角行
              for(int i=downc;i>=topc;i--)
              {
                       dsumr+=matrix[downr][i];
              	  
              }
              //扫描右下角列
              for(int i=downr;i>=topr;i--)
              {
                       dsumc+=matrix[i][downc];
              }
              if(sumr==sumc && dsumr==dsumc&&sumr==dsumr)
              {
                     max=dsumr;
              }
              return max;
    
    	}
    
    	//******************************************************
    	//方法二
    		public static void setBorderMap(int[][] m, int[][] right, int[][] down) {
    		int r = m.length;
    		int c = m[0].length;
    		if (m[r - 1][c - 1] == 1) {
    			right[r - 1][c - 1] = 1;
    			down[r - 1][c - 1] = 1;
    		}
    		for (int i = r - 2; i != -1; i--) {
    			if (m[i][c - 1] == 1) {
    				right[i][c - 1] = 1;
    				down[i][c - 1] = down[i + 1][c - 1] + 1;
    			}
    		}
    		for (int i = c - 2; i != -1; i--) {
    			if (m[r - 1][i] == 1) {
    				right[r - 1][i] = right[r - 1][i + 1] + 1;
    				down[r - 1][i] = 1;
    			}
    		}
    		for (int i = r - 2; i != -1; i--) {
    			for (int j = c - 2; j != -1; j--) {
    				if (m[i][j] == 1) {
    					right[i][j] = right[i][j + 1] + 1;
    					down[i][j] = down[i + 1][j] + 1;
    				}
    			}
    		}
    	}
    
    	public static int getMaxSize(int[][] m) {
    		int[][] right = new int[m.length][m[0].length];
    		int[][] down = new int[m.length][m[0].length];
    		setBorderMap(m, right, down);
    		for (int size = Math.min(m.length, m[0].length); size != 0; size--) {
    			if (hasSizeOfBorder(size, right, down)) {
    				return size;
    			}
    		}
    		return 0;
    	}
    
    	public static boolean hasSizeOfBorder(int size, int[][] right, int[][] down) {
    		for (int i = 0; i != right.length - size + 1; i++) {
    			for (int j = 0; j != right[0].length - size + 1; j++) {
    				if (right[i][j] >= size && down[i][j] >= size
    						&& right[i + size - 1][j] >= size
    						&& down[i][j + size - 1] >= size) {
    					return true;
    				}
    			}
    		}
    		return false;
    	}
    
    	public static int[][] generateRandom01Matrix(int rowSize, int colSize) {
    		int[][] res = new int[rowSize][colSize];
    		for (int i = 0; i != rowSize; i++) {
    			for (int j = 0; j != colSize; j++) {
    				res[i][j] = (int) (Math.random() * 2);
    			}
    		}
    		return res;
    	}
    
    	public static void printMatrix(int[][] matrix) {
    		for (int i = 0; i != matrix.length; i++) {
    			for (int j = 0; j != matrix[0].length; j++) {
    				System.out.print(matrix[i][j] + " ");
    			}
    			System.out.println();
    		}
    	}
    	public static void main(String[]args)
    	{
    		//System.out.println("Hello");
    		int[][]matrix={
                       
    		};
    
    		int[][]matrix2={
       {0,1,1,1,1},
    	                    {0,1,0,0,1},
    	                    {0,1,0,0,1},
    	                    {0,1,1,1,1},
    	                    {0,1,0,1,1}};
    
    	    int[][]matrix3={
       {1,1,1,1},
    	                    {1,0,0,1},
    	                    {1,0,0,1},
    	                    {1,1,1,1}};
            
            int[][]matrix4={
       {1,1,1},
    	                    {1,0,1},
    	                    {1,1,1},
    	                       };
    	    printMatrix(matrix);
    		System.out.println(GetMaxMatrixSize(matrix));
    		printMatrix(matrix2);
    		System.out.println(GetMaxMatrixSize(matrix2));
    		printMatrix(matrix3);
    		System.out.println(GetMaxMatrixSize(matrix3));
    		printMatrix(matrix4);
    		System.out.println(GetMaxMatrixSize(matrix4));
    
    		int[][] matrix5 = generateRandom01Matrix(7, 8);
    		printMatrix(matrix2);
    		System.out.println(getMaxSize(matrix2));
    
    
    	}
    }

![Center 1][]

[Center]: /images/20220529/03245532ce7b4ad3babf2d72a4ecd65b.png
[Center 1]: /images/20220529/1298200111ac49548328f7912e5319a6.png