每个格拆成两个点，出点连能到的点的入点，如果是箭头指向
方向费用就是0，要不就是1，源点连所有出点，所有入点连
汇点，然后费用流
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
var
n, m :longint;
map :array[..,..] of longint;
pre, other, len, cost :array[..] of longint;
last :array[..] of longint;
l :longint;
num :array[..,..] of longint;
go :array[..,..] of longint;
source, sink :longint;
ans :longint;
que, dis, father :array[..] of longint;
flag :array[..] of boolean;
function min(a,b:longint):longint;
begin
if a>b then min:=b else min:=a;
end;
procedure connect(a,b,c,d:longint);
begin
inc(l);
pre[l]:=last[a];
last[a]:=l;
other[l]:=b;
len[l]:=c;
cost[l]:=d;
end;
procedure init;
var
i, j, k :longint;
c :char;
curx, cury :longint;
begin
readln(n,m);
go[,]:=-; go[,]:=;
go[,]:=; go[,]:=-;
l:=;
for i:= to n do
begin
for j:= to m do
begin
read(c);
if c='U' then map[i,j]:= else
if c='R' then map[i,j]:= else
if c='D' then map[i,j]:= else
if c='L' then map[i,j]:=;
end;
readln;
end;
for i:= to n do
for j:= to m do num[i,j]:=((i-)*m+j);
source:=*m*n+; sink:=source+;
for i:= to n do
for j:= to m do
for k:= to do
begin
curx:=i+go[,k];
cury:=j+go[,k];
if curx= then curx:=n; if curx=n+ then curx:=;
if cury= then cury:=m; if cury=m+ then cury:=;
if map[i,j]=k then
begin
connect(num[i,j]+n*m,num[curx,cury],,);
connect(num[curx,cury],num[i,j]+n*m,,);
end else
begin
connect(num[i,j]+n*m,num[curx,cury],,);
connect(num[curx,cury],num[i,j]+n*m,,-);
end;
end;
for i:= to n do
for j:= to m do
begin
connect(source,num[i,j]+n*m,,);
connect(num[i,j]+n*m,source,,);
connect(num[i,j],sink,,);
connect(sink,num[i,j],,);
end;
{for i:=1 to n do
for j:=1 to m do
begin
connect(num[i,j],num[i,j]+n*m,1,0);
connect(num[i,j]+n*m,num[i,j],0,0);
end;}
end;
function spfa:boolean;
var
q, p, cur :longint;
h, t :longint;
begin
filldword(dis,sizeof(dis) div ,maxlongint div );
h:=; t:=;
que[]:=source; dis[source]:=;
while h<>t do
begin
h:=h mod +;
cur:=que[h];
flag[cur]:=false;
q:=last[cur];
while q<> do
begin
p:=other[q];
if len[q]> then
begin
if dis[p]>dis[cur]+cost[q] then
begin
dis[p]:=dis[cur]+cost[q];
father[p]:=q;
if not flag[p] then
begin
t:=t mod +;
que[t]:=p;
flag[p]:=true;
end;
end;
end;
q:=pre[q];
end;
end;
if dis[sink]=maxlongint div then exit(false) else exit(true);
end;
procedure update;
var
cur, low :longint;
begin
cur:=sink;
low:=maxlongint;
while cur<>source do
begin
low:=min(low,len[father[cur]]);
cur:=other[father[cur] xor ];
end;
cur:=sink;
while cur<>source do
begin
dec(len[father[cur]],low);
inc(len[father[cur] xor ],low);
inc(ans,low*cost[father[cur]]);
cur:=other[father[cur] xor ];
end;
end;
procedure main;
begin
while spfa do
update;
writeln(ans);
end;
begin
init;
main;
end.