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.

Download