題目描述
在一個(gè)n*m的只包含0和1的矩陣?yán)镎页鲆粋€(gè)不包含0的最大正方形，輸出邊長(zhǎng)。
輸入輸出格式
輸入格式： 輸入文件第一行為兩個(gè)整數(shù)n,m（1<=n,m<=100），接下來(lái)n行，每行m個(gè)數(shù)字，用空格隔開，0或1.
輸出格式： 一個(gè)整數(shù)，最大正方形的邊長(zhǎng)
輸入輸出樣例
輸入樣例#1： 4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 輸出樣例#1： 2
分析：轉(zhuǎn)移如下。 f[i,j]=min(f[i-1,j],f[i-1,j-1],f[i,j-1])+1
(如果這個(gè)格是1，則以這個(gè)格為右下角的正方形的變長(zhǎng)為周圍最小的正方形邊長(zhǎng)+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.新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
