## Editorial for Trò chơi nhặt quà

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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

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);
for i:=1 to m do begin
for j:=1 to n do begin
if c = '*' then a[i,j]:=1;
if c = '#' then a[i,j]:=-1;
end;
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
for i:=1 to m do
begin
for j:=1 to n do
begin
case ch of
'*': a[i,j]:=1;
'.': a[i,j]:=0;
'#': a[i,j]:=-1000000;
end;
end;
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;
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;
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;
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
for i:=1 to m do
begin
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.