首页 > 代码库 > 最大正方形 dp解法

最大正方形 dp解法

在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形,输出边长。

 1 var
 2   n,m,i,j,max:longint;
 3   a:array[1..100,1..100]of longint;
 4   f:array[0..100,0..100]of longint;
 5 function min(x,y,z:longint):longint;
 6 begin
 7   if x<y then
 8   if z<x then exit(z) else exit(x)
 9   else
10   if z<y then exit(z) else exit(y);
11 end;
12 begin
13   readln(m,n);
14   for i:=1 to m do
15   for j:=1 to n do
16   read(a[i,j]);
17 
18   for i:=1 to m do
19   for j:=1 to n do
20   begin
21     if a[i,j]=0 then continue;
22     f[i,j]:=min(f[i-1,j],f[i,j-1],f[i-1,j-1])+1;
23   end;
24   for i:=1 to m do
25   for j:=1 to n do
26   if f[i,j]>max then max:=f[i,j];
27   writeln(max);
28 end.

思想:以i,j为右下角矩形的最大边长取决于f[i-1,j],f[i,j-1],f[i-1,j-1]

技术分享

最大正方形 dp解法