{ Zenit CK 2011/2012, uloha e) Riesenie by Zemco Dynamicke programovanie, DP[i,j] znamena, aby najvacsi otoceny stvorec ma dolny bod v mieste [i,j]? Pocitame postupne pre zvacsujuce sa i a zvacsujuce sa j. Cas O(R*C), pamat (R*C) dala by sa zlepsit.} uses math; var i,j,R,C: integer; M: array[1..1005,1..1005] of char; DP: array[1..1005,1..1005] of integer; best: integer; {cely vstup mame zapamatany v poli o dva riadky a stlpce posunute pre zjednodusenie kodu. } begin best := 0; readln(R,C); for i:=1 to R+2 do for j:=1 to C+2 do DP[i,j] := 0; for i:=1 to R+2 do for j:=1 to C+2 do M[i,j] := '.'; for i:=1 to R do begin for j:=1 to C do read(M[i+2,j+2]); readln; end; for i:=1 to R+2 do for j:=1 to C+2 do begin if (M[i,j] = '.') then DP[i,j] := 0 else DP[i,j] := min( min( DP[i-1,j-1], DP[i-1,j+1]), min( DP[i-2,j], DP[i-1,j]) ) + 1; best := max(best, DP[i,j]); end; if (best = 0) then writeln(0) else writeln( (2*best-1)*(2*best-1) - 2*(best*(best-1) ) ); end.