Description
给一个N*N的01矩阵, 求一个面积最大的全为1的正方形子矩阵. 输出它的面积.
输入文件square.in的第一行包含一个正整数N. 接下来N行, 每行N个数, 保证不是0就是1. 每行相邻两个数之间没有空格.
Output
输出文件为square.out，仅包含一个整数表示最大的全1子正方形矩阵的面积。
2
11
11
Sample Output
4
【数据规模和约定】 80%的数据中 N<=250； 100%的数据中 N <= 1000。
题解
每一个为1的点与左上的点构成的最长正方形的边长等于左点，上点和左上点的最小值加上 1（自己的长度）。
f[i,j]:=min(f[i-1,j],f[i,j-1],f[i-1,j-1])+1
代码
var
a:
array[
0..
1000,
0..
1000]
of 0..
1;
f:
array[
0..
1000,
0..
1000]
of longint;
i,j,n,max,s:longint;
k:ansistring;
function min(x,y:longint):longint;
begin
if x>y
then exit(y)
else exit(x);
end;
begin
readln(n);
for i:=
1 to n
do
begin
readln(k);
for j:=
1 to n
do
val(k[j],a[i,j]);
end;
for i:=
1 to n
do
for j:=
1 to n
do
if a[i,j]=
1 then
begin
f[i,j]:=min(f[i-
1,j],f[i,j-
1]);
f[i,j]:=min(f[i,j],f[i-
1,j-
1]);
inc(f[i,j]);
if max<f[i,j]
then max:=f[i,j];
end;
writeln(max*max);
end.
转载请注明原文地址: https://ju.6miu.com/read-1295386.html
