Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

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.

Code mẫu của RR

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

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int f[260][130][130];
char a[130][130];
bool reach[130][130];
int m,n;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

void DFS(int x,int y)
{        
    for (int i = 0; i < 4; i++)
    {
        int px = x + dx[i],py = y + dy[i];
        if (px < 0 || px >= m || py < 0 || py >= n || reach[px][py] || a[px][py] == '#') continue;
        reach[px][py] = true;
        DFS(px,py);
    }
}

int rec(int step,int x,int y)
{
    if (f[step][x][y] > -1) return f[step][x][y];
    if (step == m + n - 1) return f[step][x][y] = 0;
    int best = 0;
    for (int px = 0; px < 2; px++)
      for (int py = 0; py < 2; py++)
      {
            int tx = x + px,ty = y + py;
            int sx = step + 1 - tx,sy = step + 1 - ty;
            if (tx > ty || ty >= n || sx >= m || a[sx][tx] == '#' || a[sy][ty] == '#') continue;
            int tmp = rec(step + 1,tx,ty);
            if (a[sx][tx] == '*') tmp++;
            if (ty > tx && a[sy][ty] == '*') tmp++;
            best = max(best,tmp);
        }
    return f[step][x][y] = best;
}

int main()
{
//    freopen("tour.in","r",stdin);
//    freopen("tour.ou","w",stdout);

    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        while (1)
        {
            scanf("%c", &a[i][j]);
            if (a[i][j] == '.' || a[i][j] == '*' || a[i][j] == '#') break;
        }
    memset(f,-1,sizeof(f));
    memset(reach,false,sizeof(reach));
    if (a[0][0] != '#') 
    {
        reach[0][0] = true; DFS(0,0);
    }
    if (!reach[m - 1][n - 1]) printf("0\n"); else
    printf("%d\n", ((a[0][0] == '*') ? 1 : 0) + rec(0,0,0));
}

Code mẫu của khuc_tuan

//{$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S+,T-,U-,V+,W-,X+,Y+,Z1}
// {$APPTYPE CONSOLE}
 {$mode delphi}

uses
    Math;

type
    Edge = class;
    List = class
        e : Edge;
        n : List;
    end;
    Node = class
        trace : Edge;
        id, fx : integer;
        ke : List;
        ken : List;
        constructor init(id, fx : integer);
    end;
    Edge = class
        u, v : Node;
        flow, cost, cap: integer;
        constructor init(u, v : Node; cost, cap : integer);
    end;

procedure AddList(var l : List; e : Edge);
var
    p : List;
begin
    p := List.Create;
    p.e := e;
    p.n := l;
    l := p;
end;

constructor Node.init(id, fx : integer);
begin
    self.id := id;
    self.fx := fx;
end;

constructor Edge.init(u, v : Node; cost, cap : integer);
begin
    self.u := u;
    self.v := v;
    self.cost := cost;
    self.cap := cap;
    self.flow := 0;
    AddList(u.ke, self);
    AddList(v.ken, self);
end;

var
    kk, i, j, nlist, nodecount, m, n : integer;
    a : array[1..150,0..300] of char;
    source, dest : array[1..150,1..150] of Node;
    start, finish : Node;
    // vs : array[1..50000] of boolean;
    EdgeList : array[1..100000] of Edge;
    res : integer;
    dist : array[0..50000] of integer;

{
function calccost(e : Edge) : integer;
begin
    calccost := e.u.fx + e.cost - e.v.fx;
end;

function dfs(u : Node) : boolean;
var
    p : List;
begin
    if u.id = finish.id then begin dfs := true; exit; end;
    if vs[u.id] then begin dfs := false; exit; end;
    vs[u.id] := true;

    p := u.ke;
    while p<>nil do
    begin
        if (calccost(p.e)=0) and (p.e.flow < p.e.cap) then
        begin
            if dfs(p.e.v) then
            begin
                inc(p.e.flow);
                res := res + p.e.cost;
                dfs := true;
                exit; 
            end;
        end; 
        p := p.n;
    end;

    p := u.ken;
    while p<>nil do
    begin
        if (calccost(p.e)=0) and (p.e.flow > 0) then
        begin
            if dfs(p.e.u) then
            begin
                dec(p.e.flow);
                res := res - p.e.cost;
                dfs := true;
                exit;
           end;
        end;
        p := p.n;
    end;
    dfs := false;
end;

procedure suanhan;
var
    dmin, i, j : integer;
    e : Edge;
begin
    dmin := 1000000000;
    for i:=1 to nlist do
    begin
        e := edgelist[i];
        if vs[e.u.id] and (not vs[e.v.id]) and (e.flow < e.cap) then
            dmin := min(dmin,calccost(e));
        if vs[e.v.id] and (not vs[e.u.id]) and (e.flow > 0) then
            dmin := min(dmin,-calccost(e));
    end;

    for i:=1 to m do
        for j:=1 to n do
        begin
            if not vs[source[i,j].id] then inc(source[i,j].fx, dmin);
            if not vs[dest[i,j].id] then inc(dest[i,j].fx, dmin);
        end;

end;
}

const
    MAXQ = 1000000;
var
    Q : array[0..MAXQ] of Node;
    lq, rq : integer;

procedure add(n : Node);
begin
    inc(rq);
    if rq > MAXQ then rq := 1;
    Q[rq] := n;
end;

function pop : Node;
begin
    pop := Q[lq];
    if lq = rq then
    begin
        lq := 1;
        rq := 0;
    end
    else
    begin
        inc(lq);
        if lq > MAXQ then lq := 1;
    end;
end;

procedure findbest;
var
    u, v : Node;
    p : List;
begin
    lq := 1; rq := 0;
    add(start);
    fillchar( dist, sizeof(dist), $1f);
    dist[start.id] := 0;
    while rq <> 0 do
    begin
        u := pop;
        p := u.ke;
        while p<>nil do begin
            if (p.e.flow < p.e.cap) and (dist[p.e.v.id] > dist[u.id] + p.e.cost) then
            begin
                dist[p.e.v.id] := dist[u.id] + p.e.cost;
                p.e.v.trace := p.e;
                add(p.e.v);
            end;
            p := p.n;
        end;

        p := u.ken;
        while p<>nil do begin
            if (p.e.flow > 0) and (dist[p.e.u.id] > dist[u.id] - p.e.cost) then
            begin
                dist[p.e.u.id] := dist[u.id] - p.e.cost;
                p.e.u.trace := p.e;
                add(p.e.u);
            end;
            p := p.n;
        end;
    end;
    v := finish;
    if dist[v.id] = dist[0] then exit;
    while v<>start do
    begin
        if v=v.trace.v then
        begin
            inc(v.trace.flow);
            inc(res, v.trace.cost);
            v := v.trace.u;
        end
        else
        begin
            dec(v.trace.flow);
            dec(res,v.trace.cost);
            v := v.trace.v;            
        end;
    end;
end;


begin
    readln(n, m);
    for i:=1 to m do
    begin
        readln(a[i]);
        move( a[i][0], a[i][1], 150); 
    end;
    nlist := 0;
    nodecount := 0;
    for i:=1 to m do
        for j:=1 to n do
        begin
            inc(nodecount);
            source[i,j] := Node.init(nodecount,1000000 - nodecount);
            inc(nodecount);
            dest[i,j] := Node.init(nodecount,1000000 - nodecount);
            if a[i,j]='*' then begin inc(nlist); EdgeList[nlist] := Edge.init(source[i,j], dest[i,j], -1, 1); end;
            if (a[i,j]='*') or (a[i,j]='.') then begin inc(nlist); EdgeList[nlist] := Edge.init(source[i,j], dest[i,j], 0, 10); end;
        end;
    for i:=1 to m do
        for j:=1 to n do
        begin
            if i<m then begin inc(nlist); EdgeList[nlist] := Edge.init(dest[i,j], source[i+1,j], 0, 10); end;
            if j<n then begin inc(nlist); EdgeList[nlist] := Edge.init(dest[i,j], source[i,j+1], 0, 10); end;
        end;

    start := source[1,1];
    finish := dest[m,n];

    for kk:=1 to 2 do findbest();

    {
    for kk:=1 to 2 do
    begin
        fillchar( vs, sizeof(vs), false);
        while(not dfs(start)) do
        begin
            suanhan;
            fillchar( vs, sizeof(vs), false);
        end;
    end;
    }
    writeln(-res);
end.