题目描述
在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。
输入输出格式
输入格式： 输入文件第一行为两个整数n,m（1<=n,m<=100），接下来n行，每行m个数字，用空格隔开，0或1.
输出格式： 一个整数，最大正方形的边长
输入输出样例
输入样例#1： 4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 输出样例#1： 2
分析：转移如下。 f[i,j]=min(f[i-1,j],f[i-1,j-1],f[i,j-1])+1
(如果这个格是1，则以这个格为右下角的正方形的变长为周围最小的正方形边长+1，画图可知)
代码：
var f,a:array [0..100,0..100] of longint; ans,i,j,n,m:longint;function min(a,b,c:longint):longint; begin if a>b then min:=b else min:=a; if c<min then min:=c; end;begin readln(n,m); for i:=1 to n do for j:=1 to m do read(a[i,j]); for i:=1 to n do for j:=1 to m do begin if a[i,j]=1 then begin f[i,j]:=min(f[i-1,j],f[i,j-1],f[i-1,j-1])+1; if f[i,j]>ans then ans:=f[i,j]; end; end; writeln(ans);end.新闻热点
疑难解答
