{ 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.
eyBaZW5pdCBDSyAyMDExLzIwMTIsIHVsb2hhIGUpCiAgUmllc2VuaWUgYnkgWmVtY28KICAgICAKICBEeW5hbWlja2UgcHJvZ3JhbW92YW5pZSwgRFBbaSxqXSB6bmFtZW5hLCBhYnkgbmFqdmFjc2kKICBvdG9jZW55IHN0dm9yZWMgbWEgZG9sbnkgYm9kIHYgbWllc3RlIFtpLGpdPwogIFBvY2l0YW1lIHBvc3R1cG5lIHByZSB6dmFjc3VqdWNlIHNhIGkgYSB6dmFjc3VqdWNlIHNhIGouCiAgQ2FzIE8oUipDKSwgcGFtYXQgKFIqQykgZGFsYSBieSBzYSB6bGVwc2l0Ln0KdXNlcyBtYXRoOwp2YXIgaSxqLFIsQzogaW50ZWdlcjsKICAgIE06IGFycmF5WzEuLjEwMDUsMS4uMTAwNV0gb2YgY2hhcjsKICAgIERQOiBhcnJheVsxLi4xMDA1LDEuLjEwMDVdIG9mIGludGVnZXI7CiAgICBiZXN0OiBpbnRlZ2VyOwp7Y2VseSB2c3R1cCBtYW1lIHphcGFtYXRhbnkgdiBwb2xpIG8gZHZhIHJpYWRreSBhIHN0bHBjZSBwb3N1bnV0ZQogcHJlIHpqZWRub2R1c2VuaWUga29kdS4gfQpiZWdpbgogIGJlc3QgOj0gMDsKICByZWFkbG4oUixDKTsKICBmb3IgaTo9MSB0byBSKzIgZG8gZm9yIGo6PTEgdG8gQysyIGRvIERQW2ksal0gOj0gMDsKICBmb3IgaTo9MSB0byBSKzIgZG8gZm9yIGo6PTEgdG8gQysyIGRvIE1baSxqXSA6PSAnLic7CiAgZm9yIGk6PTEgdG8gUiBkbwogIGJlZ2luCiAgICBmb3Igajo9MSB0byBDIGRvIHJlYWQoTVtpKzIsaisyXSk7CiAgICByZWFkbG47CiAgZW5kOwogIGZvciBpOj0xIHRvIFIrMiBkbyBmb3Igajo9MSB0byBDKzIgZG8KICBiZWdpbgogICAgaWYgKE1baSxqXSA9ICcuJykgdGhlbiBEUFtpLGpdIDo9IDAKICAgIGVsc2UgRFBbaSxqXSA6PSBtaW4oIG1pbiggRFBbaS0xLGotMV0sIERQW2ktMSxqKzFdKSwgbWluKCBEUFtpLTIsal0sIERQW2ktMSxqXSkgKSArIDE7CiAgICBiZXN0IDo9IG1heChiZXN0LCBEUFtpLGpdKTsKICBlbmQ7CiAgaWYgKGJlc3QgPSAwKSB0aGVuIHdyaXRlbG4oMCkKICBlbHNlIHdyaXRlbG4oICgyKmJlc3QtMSkqKDIqYmVzdC0xKSAtIDIqKGJlc3QqKGJlc3QtMSkgKSApOwplbmQu