#include<cstdio>
#include<iostream>
#include<cstring>
#define M 10000
#define inf 2139062143
using namespace std;
int cnt=,n,m,ans,T,d[M],q[*M],f[M],head[M],next[*M],u[*M],v[*M],w[*M],fro[*M],fr[M];
int mp[][],xx[]={,,,-},yy[]={-,,,};
void jia1(int a1,int a2,int a3,int a4)
{
cnt++;
next[cnt]=head[a1];
head[a1]=cnt;
fro[cnt]=a1;
u[cnt]=a2;
v[cnt]=a3;
w[cnt]=a4;
}
void jia(int a1,int a2,int a3,int a4)
{
jia1(a1,a2,a3,a4);
jia1(a2,a1,,-a4);
return;
}
bool spfa()
{
memset(d,,sizeof(int)*(T+));
d[]=;
f[]=;
q[]=;
int h=,t=;
for(;h<t;)
{
h++;
int p=q[h];
f[p]=;
for(int i=head[p];i;i=next[i])
if(v[i]&&d[u[i]]>d[p]+w[i])
{
d[u[i]]=d[p]+w[i];
fr[u[i]]=i;
if(!f[u[i]])
{
f[u[i]]=;
t++;
q[t]=u[i];
}
}
}
if(d[T]!=inf)
return ;
return ;
}
void mcf()
{
int mx=inf;
for(int i=fr[T];i;i=fr[fro[i]])
mx=min(mx,v[i]);
for(int i=fr[T];i;i=fr[fro[i]])
{
v[i]-=mx;
v[i^]+=mx;
ans+=mx*w[i];
}
return;
}
int main()
{
char ch[];
scanf("%d%d",&n,&m);
T=n*m*+;
for(int i=;i<=n;i++)
{
scanf("%s",ch+);
for(int j=;j<=m;j++)
{
if(ch[j]=='L')
mp[i][j]=;
if(ch[j]=='R')
mp[i][j]=;
if(ch[j]=='D')
mp[i][j]=;
if(ch[j]=='U')
mp[i][j]=;
}
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
jia(,(i-)*m+j,,);
jia((i-)*m+n*m+j,T,,);
for(int k=;k<;k++)
{
int nx=i+xx[k],ny=j+yy[k];
if(!nx)
nx=n;
if(!ny)
ny=m;
if(nx>n)
nx=;
if(ny>m)
ny=;
if(k==mp[i][j])
jia((i-)*m+j,(nx-)*m+ny+n*m,,);
else
jia((i-)*m+j,(nx-)*m+ny+n*m,,);
}
}
for(;spfa();)
mcf();
printf("%d\n",ans);
return ;
}
循环格出入度都等于1，与一开始方向不同的加上费用，跑费用流，