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.

Download