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