边界都是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)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, Max=0, s1, s2;
    cin>>n;
    int a[n+1][n+1], row[n+1][n+1], col[n+1][n+1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            row[i][j] = row[i][j-1] + a[i][j];
            col[i][j] = col[i-1][j] + a[i][j];
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            for(int l=Max+1;l<=min(n-i+1,n-j+1);l++){
                s1 = row[i][j+l-1] - row[i][j-1];
                s2 = col[i+l-1][j] - col[i-1][j];
                if(s1!=l || s2!=l)
                    break;
                s1 = row[i+l-1][j+l-1] - row[i+l-1][j-1];
                s2 = col[i+l-1][j+l-1] - col[i-1][j+l-1];
                if(s1==l && s2==l)
                    Max = max(Max, l);
            }
        }
    cout<<Max<<endl;    
    return 0;
}

发表于 2020-02-20 01:13:08 回复(1)

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)

牛客79631828号

import java.util.*;

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(getMaxMatrix(m));
        sc.close();
    }
    
    //以每一个点为左上角，尝试是否存在一个长度为1~N的正方形
    //由于使用了预处理，时间复杂度变为O(N^3)
    public static int getMaxMatrix(int[][] m) {
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0)
            return 0;
        if (m.length == 1)
            return m[0][0] == 1 ? 1 : 0;
        int len = m.length;
        int[][] right = new int[len][len];
        int[][] down = new int[len][len];
        preProcess(right, down, m);
        int res = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                for (int n = 1; n <= len; n++) {
                    if (hasNSquare(right, down, n, i, j))
                        res = Math.max(res, n);
                }
            }
        }
        return res;
    }
    
    //预处理，使right[i][j]代表从m[i][j]开始往右最多出现了几个连续的1
    //down[i][j]代表从m[i][j]开始往下最多出现了几个连续的1
    public static void preProcess(int[][] right, int[][] down, int[][] m) {
        int len = m.length-1;
        right[len][len] = m[len][len] == 1 ? 1 : 0;
        down[len][len] = m[len][len] == 1 ? 1 : 0;
        for (int i = len-1; i >= 0; i--) {
            if (m[i][len] == 1) {
                right[i][len] = 1;
                down[i][len] = 1 + down[i+1][len];
            }
            if (m[len][i] == 1) {
                right[len][i] = 1 + right[len][i+1];
                down[len][i] = 1;
            }
        }
        for (int i = len-1; i >= 0; i--) {
            for (int j = len - 1; j >= 0; j--) {
                if (m[i][j] == 1) {
                    right[i][j] = right[i][j+1] + 1;
                    down[i][j] = down[i+1][j] + 1;
                }
            }
        }
    }
    
    //判断以m[i][j]为左上角，边长为n且边界都是1的正方形是否存在
    public static boolean hasNSquare(int[][] right, int[][] down, int n, int i, int j) {
        if (right[i][j] >= n && down[i][j] >= n) {
            if (i + n - 1 < right.length && j + n - 1 < down.length) {
                if (right[i+n-1][j] >= n && down[i][j+n-1] >= n)
                    return true;
            }
        }
        return false;
    }
}

发表于 2021-08-22 02:08:21 回复(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)

AnnaSophia_Robb

leetcode上原题，dp[i][j]表示左上角的矩阵范围内以dp[i][j]作为右下角的正方形的最大边长, 参考木桶最短边原理；

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; scanf("%d", &n);
    vector<vector<int>> m(n, vector<int>(n));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &m[i][j]);
        }
    }
    int ans = 0;
    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(m[i][j] == 1){
                dp[i+1][j+1] = min(min(dp[i][j+1], dp[i+1][j]), dp[i][j]) + 1;
                ans = max(ans, dp[i+1][j+1]);
            }
        }
    }
    printf("%d", ans);
    return 0;
}

编辑于 2020-02-19 00:08:35 回复(1)

皮蛋秀柚秋

#include<bits/stdc++.h>
using namespace std;
void setBorderMap(vector<vector<int>>& matrix,vector<vector<int>>& right,vector<vector<int>>& down)
{

    int n = matrix.size();
    for(int i=n-1;i>=0;--i)
    {
        for(int j=n-1;j>=0;--j)
        {
            if(i==n-1 && j==n-1)
            {
                right[i][j] = matrix[i][j] ? 1 : 0;
                down[i][j] = matrix[i][j] ? 1 : 0;
            }
            else if(i==n-1)
            {
                down[i][j] = matrix[i][j] ? 1 : 0;
                right[i][j] = matrix[i][j] ? right[i][j+1] + 1 : 0;
            }
            else if(j==n-1)
            {
                right[i][j] = matrix[i][j] ? 1 : 0;
                down[i][j] = matrix[i][j] ? down[i+1][j] + 1 : 0;
            }
            else
            {
                right[i][j] = matrix[i][j] ? right[i][j+1] + 1 : 0;
                down[i][j] = matrix[i][j] ? down[i+1][j] + 1 : 0;
            }
        }
    }
}
bool hasSizeOfBorder(int i,int j,vector<vector<int>>& right,vector<vector<int>>& down,int size)
{
    int n = right.size();
    if(n-i>=size && n-j>=size && right[i][j]>=size && down[i][j]>=size && right[i+size-1][j]>=size && down[i][j+size-1]>=size)
        return true;
    else return false;
}
int main()
{
    int n;
    cin>>n;
    vector<vector<int>>matrix(n,vector<int>(n,0));
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            cin>>matrix[i][j];
    vector<vector<int>>right(n,vector<int>(n,0));
    vector<vector<int>>down(n,vector<int>(n,0));
    setBorderMap(matrix,right,down);
    int ans = 0;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            for(int size = 1;size<=n;++size)
            {
                if(hasSizeOfBorder(i,j,right,down,size))
                    ans = max(ans,size);
            }
        }
    }
    cout<<ans;
    return 0;
}

发表于 2020-02-11 21:32:48 回复(0)

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

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题