SCOLLECT - Trò chơi nhặt quà
Tác giả: ladpro98
Ngôn ngữ: Pascal
program SCOLLECT;
uses math;
const fi = '';
maxn = 135;
oo = trunc(1e9);
dx : array[1..2] of longint = (-1,0);
dy : array[1..2] of longint = (0,-1);
var a:array[0..maxn,0..maxn] of longint;
f:array[0..maxn,0..maxn,0..maxn] of longint;
chk:array[0..maxn,0..maxn,0..maxn] of boolean;
inp:text; c:char;
m,n,i,j,res:longint;
Function DP(i,j,x,y:longint):longint;
var d1,d2,xx,yy,ii,jj,plus:longint;
begin
if chk[i,j,x] then exit(f[i,j,x]);
chk[i,j,x] := true;
if (i = 1) and (j = 1) then begin
f[i,j,x] := a[1,1];
exit(a[1,1]);
end;
if (i<1) or (j<1) or (x<1) or (y<1)
or (i>m) or (j>n) or (x>m) or (y>n)
or (a[i,j] = -1) or (a[x,y] = -1) then begin
f[i,j,x] := -oo;
exit(-oo);
end;
if (i = x) and (j = y) then plus := a[i,j]
else plus := a[i,j] + a[x,y];
f[i,j,x] := -oo;
for d1:=1 to 2 do
for d2:=1 to 2 do begin
ii := i + dx[d1]; jj := j + dy[d1];
xx := x + dx[d2]; yy := y + dy[d2];
f[i,j,x] := max(f[i,j,x], DP(ii, jj, xx, yy) + plus);
end;
exit(f[i,j,x]);
end;
procedure Input;
begin
assign(inp,fi);reset(inp);
readln(inp,n,m);
for i:=1 to m do begin
for j:=1 to n do begin
read(inp,c);
if c = '*' then a[i,j]:=1;
if c = '#' then a[i,j]:=-1;
end;
readln(inp);
end;
end;
begin
Input;
res := max(0,DP(m,n,m,n));
write(res);
end.