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

输入

输出

备注:

算法知识视频讲解

总之就是非常可爱

发表于 2022-02-09 17:29:12

//本题首先对矩阵进行预处理 //申请一个同样大小的预处理数组 //数组的每一个位置有两个变量一个代表从当前行由左到当前位置有多少连续1 //另一个代表从上到当前位置有多少个连续的1 #include<bits/stdc++.h> using namespace std; struct 展开全文

SunshineO

发表于 2020-08-15 16:32:36

n = int(input()) M = [] for _ in range(n): M.append(list(map(int, input().split()))) max_len = 0 def dfs_r(x,y,max_r): # 寻找右边界 if y < n: 展开全文

WYJ96

发表于 2021-08-11 20:15:28

import java.util.Scanner; public class Main { /*1、一共N*N个位置，复杂度O(N^2) 2、对于每一个位置，检测是否有边长为1---N的正方形复杂度O(N) 3、如何检测，复杂度O(1) 时间复杂度为O(n^3) 空展开全文

星晨

发表于 2020-11-15 12:53:14

题目描述给定一个N \times NN×N的矩阵matrix，在这个矩阵中，只有0和1两种值，返回边框全是1的最大正方形的边长长度、例如0 1 1 1 10 1 0 0 10 1 0 0 10 1 1 1 10 1 0 1 1其中，边框全是1的最大正方形的大小为4 \times 44×4，所以返回4 展开全文