1 #include<bits/stdc++.h>
2 using namespace std;
3 #define INF 1e9
4 struct node
5 {
6 int begin,end,cap,value,next;
7 }edge[2710];
8 int cnt,Head[620],c,S,T,ans,q[620],dis[620],from[620];
9 bool vis[620];
10 char a[20][20];
11 int fx[5]={0,0,1,-1};
12 int fy[5]={1,-1,0,0};
13 void addedge(int bb,int ee,int cc,int vv)
14 {
15 edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].cap=cc;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;
16 }
17 void addedge1(int bb,int ee,int cc,int vv)
18 {
19 addedge(bb,ee,cc,vv);addedge(ee,bb,0,-vv);
20 }
21 int xy(int x,int y){return (x-1)*c+y;}
22 int SPFA()
23 {
24 int head,tail,i,u,v;
25 head=0;tail=1;q[tail]=S;
26 for(i=1;i<=T;i++)dis[i]=INF;dis[S]=0;
27 memset(vis,false,sizeof(vis));vis[S]=true;
28 while(head!=tail)
29 {
30 head++;if(head==610)head=0;
31 u=q[head];
32 for(i=Head[u];i!=-1;i=edge[i].next)
33 {
34 if(edge[i].cap>0)
35 {
36 v=edge[i].end;
37 if(dis[u]+edge[i].value<dis[v])
38 {
39 dis[v]=dis[u]+edge[i].value;
40 from[v]=i;
41 if(vis[v]==false)
42 {
43 vis[v]=true;
44 tail++;if(tail==610)tail=0;
45 q[tail]=v;
46 }
47 }
48 }
49 }
50 vis[u]=false;
51 }
52 if(dis[T]<INF)return 1;
53 else return 0;
54 }
55 void MCF()
56 {
57 int F=INF,i;
58 for(i=from[T];i;i=from[edge[i].begin])F=min(F,edge[i].cap);
59 for(i=from[T];i;i=from[edge[i].begin]){edge[i].cap-=F,edge[i^1].cap+=F;ans+=F*edge[i].value;}
60 //ans+=dis[T];
61 memset(from,0,sizeof(from));
62 }
63 int main()
64 {
65 int r,i,j,k,XY,x1,y1;
66 scanf("%d %d",&r,&c);
67 for(i=1;i<=r;i++)
68 {
69 scanf("\n%s",a[i]+1);
70 }
71 S=601;T=602;
72 memset(Head,-1,sizeof(Head));cnt=1;
73 for(i=1;i<=r;i++)
74 {
75 for(j=1;j<=c;j++)
76 {
77 XY=xy(i,j);
78 addedge1(S,XY,1,0);
79 addedge1(XY+300,T,1,0);
80 for(k=0;k<=3;k++)
81 {
82 x1=i+fx[k];
83 y1=j+fy[k];
84 if(x1<1)x1=r;if(x1>r)x1=1;
85 if(y1<1)y1=c;if(y1>c)y1=1;
86 if(a[i][j]==‘U‘&&k==3){addedge1(XY,xy(x1,y1)+300,1,0);continue;}
87 if(a[i][j]==‘D‘&&k==2){addedge1(XY,xy(x1,y1)+300,1,0);continue;}
88 if(a[i][j]==‘L‘&&k==1){addedge1(XY,xy(x1,y1)+300,1,0);continue;}
89 if(a[i][j]==‘R‘&&k==0){addedge1(XY,xy(x1,y1)+300,1,0);continue;}
90 addedge1(XY,xy(x1,y1)+300,1,1);
91 }
92 /*if(a[i][j]==‘U‘)
93 {
94 if(i-1>=1)addedge1(XY,xy(i-1,j)+300,1,0);
95 else addedge1(XY,xy(r,j)+300,1,0);
96 }
97 else if(a[i][j]==‘D‘)
98 {
99 if(i+1<=r)addedge1(XY,xy(i+1,j)+300,1,0);
100 else addedge1(XY,xy(1,j)+300,1,0);
101 }
102 else if(a[i][j]==‘L‘)
103 {
104 if(j-1>=1)addedge1(XY,xy(i,j-1)+300,1,0);
105 else addedge1(XY,xy(i,c)+300,1,0);
106 }
107 else
108 {
109 if(j+1<=c)addedge1(XY,xy(i,j+1)+300,1,0);
110 else addedge1(XY,xy(i,1)+300,1,0);
111 }*/
112 }
113 }
114 ans=0;
115 while(SPFA())MCF();
116 printf("%d",ans);
117 return 0;
118 }
