SCOLLECT - Trò chơi nhặt quà
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
{$Mode objFPC}
uses math;
const
FINP='';
FOUT='';
MAXN=130;
var
f1,f2:text;
test,m,n:longint;
a:array[0..MAXN,0..MAXN] of longint;
d:array[0..MAXN,0..MAXN,0..MAXN] of longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1); close(f2);
end;
procedure inp;
var
ch:char;
i,j:longint;
begin
readln(f1,n,m);
for i:=1 to m do
begin
for j:=1 to n do
begin
read(f1,ch);
case ch of
'*': a[i,j]:=1;
'.': a[i,j]:=0;
'#': a[i,j]:=-1000000;
end;
end;
readln(f1);
end;
end;
procedure solve;
var
row,i,j:longint;
begin
for i:=1 to n do
d[1,1,i]:=d[1,1,i-1]+a[1,i];
for i:=2 to n do
for j:=i to n do
d[1,i,j]:=d[1,i-1,j];
for row:=2 to m do
begin
for i:=1 to n do
d[row,i,i]:=d[row-1,i,i]+a[row,i];
for i:=1 to n do
for j:=i+1 to n do
d[row,i,j]:=d[row-1,i,j]+a[row,i]+a[row,j];
for i:=1 to n do
for j:=i+2 to n do
d[row,i+1,j]:=max(d[row,i+1,j],d[row,i,j]+a[row,i+1]);
for i:=2 to n do
d[row,i,i]:=max(d[row,i,i],d[row,i-1,i]);
for i:=2 to n do
d[row,i,i]:=max(d[row,i,i],d[row,i-1,i-1]+a[row,i]);
for i:=1 to n do
for j:=i to n-1 do
d[row,i,j+1]:=max(d[row,i,j+1],d[row,i,j]+a[row,j+1]);
end;
end;
procedure ans;
begin
if d[m,n,n]<0 then d[m,n,n]:=0;
writeln(f2,d[m,n,n]);
end;
begin
openF;
// readln(f1,test);
test:=1;
for test:=1 to test do
begin
inp;
solve;
ans;
end;
closeF;
end.