题目概述
在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。
1<=n,m<=100
解题思路
在读入的时候，如果读入了1，记下每行中到这个1之前有多少个连续的1。
我采用的是模拟正方形的右下角，向上扩展，记下合法边长的最大值。
合法边长为向上扩展的过程中扩展次数和扩展路径上记录值的最小值之间较小的数。
注意边界，差值可能为负数。
时间复杂度:O(n*m^2)
空间复杂度:O(n*m)
源程序
var a,b:array[0..102,0..102]of longint; i,j,n,m,ans,now,x:longint; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; begin readln(n,m); for i:=1 to n do begin for j:=1 to m do begin read(a[i,j]); if a[i,j]=1 then b[i,j]:=b[i,j-1]+1; end; readln; end; ans:=0; for i:=1 to n do for j:=1 to m do begin if a[i,j]=0 then continue; now:=b[i,j]; x:=i; while x>=1 do begin if now>b[x,j] then now:=b[x,j]; ans:=max(ans,min(now,i-x+1)); dec(x); end; end; write(ans); end.
