题目背景
一个循环格就是一个矩阵,其中所有元素为箭头,指向相邻四个格子。每个元素有一个坐标(行,列),其中左上角元素坐标为(0,0)。给定一个起始位(r,c),你可以沿着箭头方向在格子间行走。即:如果(r,c)是一个左箭头，那么走到(r,c-1);如果是一个右箭头,走到(r,c+1);如果是上箭头,走到(r-1,c);如果是下箭头,走到(r+1,c)。每一行和每一列都是循环的,即如果走出边界,你会出现在另一侧。比如在一个5*5的循环格里,从(3,0)向左走会出现在(3,4)。

题目描述
一个完美的循环格是这样定义的:对于任意一个起始位置,你都可以沿着箭头最终回到起始位置。如果一个循环格不满足完美,你可以随意修改任意一个元素的箭头直到完美。例如下图,左边不是一个完美的循环格,因为只有从(1,1),(1,2),(2,0),(2,3)出发才会回到起始位置。通过修改其中两个箭头,可以得到右图,一个完美的循环格。

给定一个循环格,你需要计算最少需要修改多少个元素使其完美。

输入格式
第一行两个整数R和C,表示循环格的行和列。接下来R行,每一行包含C个字符LRUD表示左右上下

输出格式
一个整数,表示最少需要修改多少个元素使得给定的循环格完美。

输入输出样例
输入 #1复制
4 4
RRRD
URDD
UULD
ULLL
输出 #1复制
0
输入 #2复制
3 4
RRRD
URLL
LRRR
输出 #2复制
2
说明/提示
数据范围
30%的数据，1 ≤ R, C ≤ 7

100%的数据，1 ≤ R, C ≤ 15

我们画画图可以发现，每个点必须要有入度，那么所有点构成了许多个强连通分量，所以如果可以循环，那么必须是对于每个点来说，一个出度，一个入度。

所以题目变成了，让所有点入度为1，的最小代价，费用流即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e4+10,M=1e5+10,inf=0x3f3f3f3f;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
const char ch[]={'R','D','L','U'};
int n,m,v[N],e[N],d[N],s,t;
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
char g[20][20];
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=d; flow[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
inline int id(int x,int y){return (x-1)*m+y;}
inline int spfa(){
	memset(d,inf,sizeof d); d[s]=0; queue<int> q;	q.push(s);
	int vis[N]={0}; vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop(); vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u; e[to[i]]=i;
				if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=inf;
}
int EK(){
	int res=0;
	while(spfa()){
		int mi=inf;
		for(int i=t;i!=s;i=v[i])	mi=min(flow[e[i]],mi);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		res+=mi*d[t];
	}
	return res;
}
signed main(){
	cin>>n>>m;	for(int i=1;i<=n;i++)	scanf("%s",g[i]+1); t=n*m*2+1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			add(s,id(i,j),1,0); add(id(i,j)+n*m,t,1,0);
			for(int k=0;k<4;k++){
				int tx=(i+dx[k]+n-1)%n+1,ty=(j+dy[k]+m-1)%m+1;
				add(id(i,j),id(tx,ty)+n*m,1,g[i][j]!=ch[k]);
			}
		}
	}
	cout<<EK()<<endl;
	return 0;
}