題目描述
在一個n*m的只包含0和1的矩陣里找出一個不包含0的最大正方形，輸出邊長。
輸入輸出格式
輸入格式： 輸入文件第一行為兩個整數n,m（1<=n,m<=100），接下來n行，每行m個數字，用空格隔開，0或1.
輸出格式： 一個整數，最大正方形的邊長
輸入輸出樣例
輸入樣例#1： 4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 輸出樣例#1： 2
分析：轉移如下。 f[i,j]=min(f[i-1,j],f[i-1,j-1],f[i,j-1])+1
(如果這個格是1，則以這個格為右下角的正方形的變長為周圍最小的正方形邊長+1，畫圖可知)
代碼：
var f,a:array [0..100,0..100] of longint; ans,i,j,n,m:longint;function min(a,b,c:longint):longint; begin if a>b then min:=b else min:=a; if c<min then min:=c; end;begin readln(n,m); for i:=1 to n do for j:=1 to m do read(a[i,j]); for i:=1 to n do for j:=1 to m do begin if a[i,j]=1 then begin f[i,j]:=min(f[i-1,j],f[i,j-1],f[i-1,j-1])+1; if f[i,j]>ans then ans:=f[i,j]; end; end; writeln(ans);end.新聞熱點
疑難解答
