首页 > 代码库 > 最大正方形 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解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。