题解 P1387 【最大正方形】

ChoHakuNe · 2017-10-15 21:36:31 · 题解

老实用dp的我...

f[i,j]表示以(i,j)为右下角的最大正方形

状态转移方程为f[i,j]=min(f[i-1,j-1],f[i-1,j],f[i,j-1])，且a[i,j]不为0

当这个(不为0的)点左边、上边、左上的点均能构成边长为x的正方形时，再加上这个点就可以构成边长为x+1的正方形了

program jz;
uses math;//调用math库，就能直接用min函数了
var a:array[1..100,1..100] of integer;
    f:array[0..100,0..100] of integer;
    n,m,i,j,max:integer;
begin
 read(n,m);
 for i:=1 to n do
  for j:=1 to m do
   begin
    read(a[i,j]);
    if a[i,j]=0 then continue;//这个点是0直接不考虑
    f[i,j]:=min(min(f[i-1,j-1],f[i,j-1]),f[i-1,j])+1;//状态转移方程
    if f[i,j]>max then max:=f[i,j];//顺便找答案
   end;
 write(max);
end.