首页 > 试题广场 >

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

[编程题]边界都是1的最大正方形大小

热度指数：1985 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 $N \times N$ 的矩阵matrix，在这个矩阵中，只有0和1两种值，返回边框全是1的最大正方形的边长长度、

例如

0 1 1 1 1

0 1 0 0 1

0 1 1 1 1

0 1 0 1 1

其中，边框全是1的最大正方形的大小为 $4 \times 4$ ，所以返回4

[要求]

时间复杂度为

，空间复杂度为

输入描述:

第一行一个整数N。表示矩阵的长宽。
接下来N行，每行N个整数表示矩阵内的元素

输出描述:

输出一个整数表示答案

示例1

输入

输出

备注:

算法知识视频讲解

Java

pein531

这个题还挺暴力的，预先计算一下每个位置包括自己在内，向右和向下有多少个连续的1，将结果存在两个N*N的矩阵right和down中，使得空间复杂度在O(N²)。然后遍历所有位置O(N²)，以这些位置为正方形的左上角，固定住左上角后从长到短遍历边长的可能性O(N)，利用right和down两个矩阵检查边长是否合法，合法就跳出边长的枚举，去到下一个可能的左上角位置，总共的时间复杂度为O(N³)。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];
        for(int i = 0; i < n; i++){
            String[] line = br.readLine().split(" ");
            for(int j = 0; j < n; j++) arr[i][j] = Integer.parseInt(line[j]);
        }
        int[][] right = new int[n][n];
        int[][] down = new int[n][n];
        for(int i = n - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                if(i == n - 1)
                    down[i][j] = arr[i][j];
                else
                    down[i][j] = arr[i][j] == 0? 0: down[i + 1][j] + 1;
                if(j == n - 1)
                    right[i][j] = arr[i][j];
                else
                    right[i][j] = arr[i][j] == 0? 0: right[i][j + 1] + 1;
            }
        }
        int maxEdgeLength = 1;
        // 枚举正方形左上角顶点的位置
        for(int row = 0; row < n; row++){
            for(int col = 0; col < n; col++){
                if(arr[row][col] == 0) continue;
                for(int border = Math.min(n - row, n - col); border >= 1; border--){
                    // 看边长够不够border
                    if(right[row][col] >= border && down[row][col] >= border && right[row + border - 1][col] >= border && down[row][col + border - 1] >= border){
                        maxEdgeLength = Math.max(maxEdgeLength, border);
                        break;
                    }
                }
            }
        }
        System.out.println(maxEdgeLength);
    }
}

编辑于 2021-11-22 22:21:40 回复(0)

Java

薛猫201811222034408

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] m = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                m[i][j] = sc.nextInt();
            }
        }
        System.out.println(getMaxBorderSize(m));
    }

    public static void preprocess(int[][] m, int[][] right, int[][] down) {
        int row = m.length, col = m[0].length;

        // set the last column of right and the last row of down
        for (int i = 0; i < row; i++) {
            right[i][col - 1] = m[i][col - 1];
        }
        for (int j = 0; j < col; j++) {
            down[row - 1][j] = m[row - 1][j];
        }

        // set the last row of right[][]
        for (int j = col - 2; j >= 0; j--) {
            if (m[row - 1][j] == 1) {
                right[row - 1][j] = right[row - 1][j + 1] + 1;
            } else {
                right[row - 1][j] = 0;
            }
        }

        // set the last column of down[][]
        for (int i = row - 2; i >= 0; i--) {
            if (m[i][col - 1] == 1) {
                down[i][col - 1] = down[i + 1][col - 1] + 1;
            } else {
                down[i][col - 1] = 0;
            }
        }

        // set the other position of right[][]  and down[][]
        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                if (m[i][j] == 1) {
                    right[i][j] = right[i][j + 1] + 1;
                    down[i][j] = down[i + 1][j] + 1;
                } else {
                    right[i][j] = 0;
                    down[i][j] = 0;
                }
            }
        }
    }

    public static int getMaxBorderSize(int[][] m) {
        int[][] right = new int[m.length][m[0].length];
        int[][] down = new int[m.length][m[0].length];
        preprocess(m, right, down);
        int n = Math.min(m.length, m[0].length);
        for (int size = n; size >= 0; size--) {
            if (hasSizeOfBorder(size, right, down)) {
                return size;
            }
        }
        return 0;
    }

    private 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;
    }
}

发表于 2021-04-13 11:18:23 回复(0)

Java

眼睛想旅行121

import java.util.Scanner;

public class Main{

    //根据m矩阵，设置right与down矩阵，right[i][j]表示m[i][j]的右边有多少个连续的1，包括自身
    //down[i][j]表示m[i][j]的下边有多少个连续的1，包括自身
    public static void setRightAndDown(int[][] m, int [][] right, int[][] down) {
        int rowNum = m.length;
        int colNum = m[0].length;
        //初始化右下角位置
        right[rowNum - 1][colNum - 1] = m[rowNum - 1][colNum - 1];
        down[rowNum - 1][colNum - 1] = m[rowNum - 1][colNum - 1];
        //初始化最后一行
        for (int col = colNum - 2; col >= 0; col--) {
            if (m[rowNum - 1][col] == 1) {
                right[rowNum - 1][col] = right[rowNum - 1][col + 1] + 1;
                down[rowNum - 1][col] = 1;
            }
        }
        //初始化最后一列
        for (int row = rowNum - 2; row >= 0; row--) {
            if (m[row][colNum - 1] == 1) {
                right[row][colNum - 1] = 1;
                down[row][colNum - 1] = down[row + 1][colNum - 1] + 1;
            }
        }
        //其他位置，从右向左，从下到上设置值
        for (int row = rowNum - 2; row >= 0; row--) {
            for (int col = colNum - 2; col >= 0; col--) {
                if (m[row][col] == 1) {
                    right[row][col] = right[row][col + 1] + 1;
                    down[row][col] = down[row + 1][col] + 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];
        setRightAndDown(m, right, down);

        for (int length = Math.min(m.length, m[0].length); length >= 1; length--) {
            //对于每个边长，看是否存在以该值作为边长的矩阵，满足四周全为1
            //因为要找最大边长，所以从大到小找
            if (hasSizeOfBorder(length, right, down)) {
                return length;
            }
        }
        return 0;
    }

    //该函数实现传入一个边长值，根据right与down矩阵，判断是否存在正方形满足四周全为1
    public static boolean hasSizeOfBorder(int length, int[][] right, int[][] down) {
        for (int row = 0; row + length - 1 <= right.length - 1; row++) {
            for(int col = 0; col + length - 1 <= right[0].length - 1; col++) {
                //row,col代表左上方的位置，要求左上方处下边最少有连续的length个1，右边最少有连续的length个1
                //[row + length - 1][col]代表左下角，要求该点右边最少有连续的length个1
                //[row][col + length - 1]代表右上角，要求该点下边最少有连续的length个1
                //这样便确立了四个边
                if (right[row][col] >= length && down[row][col] >= length
                        && right[row + length - 1][col] >= length
                        && down[row][col + length - 1] >= length) {
                    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) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[][] arr=new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                arr[i][j]=sc.nextInt();
            }
        }
        System.out.println(getMaxSize(arr));
    }
}

发表于 2021-03-19 15:43:08 回复(0)

Java

小星教授

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
        int[][] arr = new int[n][n];
        for(int i=0;i<n;i++){
        	for(int j=0;j<n;j++) {
        		arr[i][j] = scanner.nextInt();
        	}
        }
        
        int[][] right = new int[n][n];
        int[][] down = new int[n][n];
        for(int i=n-1;i>=0;i--) {
        	for(int j=n-1;j>=0;j--) {
        		if(i==n-1) {
        			down[i][j] = arr[i][j];
        		}else {
        			down[i][j] = arr[i][j]==0? 0:down[i+1][j]+1;
        		}
        		
        		if(j==n-1) {
        			right[i][j] = arr[i][j];
        		}else {
        			right[i][j] = arr[i][j]==0? 0:right[i][j+1]+1;
        		}
        	}
        }
        
        int max = 0;
        for(int i=0;i<n;i++){
        	for(int j=0;j<n;j++) {
        		int m = Math.min(down[i][j], right[i][j]);
        		for(int k=m-1;k>=0;k--) {
        			if(right[i+k][j] >= k+1 && down[i][j+k]>=k+1) {
        				max = Math.max(max, k+1);
        				break;
        			}
        		}
        	}
        }
      
        
        System.out.println(max);
        
	}
	
	
}

发表于 2019-10-24 18:57:17 回复(0)