C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 984K, 提交时间: 2019-03-16 14:47:25

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define LL long long
#define INF 1000000000
using namespace std;
struct edge_type
{
	int next,from,to,f,c;
}e[20500];
int r,c,x,y,xx,yy,cnt=1,s,t,ans,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
int dis[500],f[500][500],head[500],pre[500];
bool inq[500];
char ch;
queue<int>q;
void add_edge(int a,int b,int flow,int cost)
{
	e[++cnt]=(edge_type){head[a],a,b,flow,cost};head[a]=cnt;
	e[++cnt]=(edge_type){head[b],b,a,0,-cost};head[b]=cnt;
}
bool spfa()
{
	memset(inq,false,sizeof(inq));
	F(i,0,499) dis[i]=INF;
	dis[s]=0;
	inq[s]=true;
	q.push(s);
	while (!q.empty())
	{
		int tmp=q.front();
		q.pop();
		inq[tmp]=false;
		for (int p=head[tmp];p;p=e[p].next)
		{
			if (e[p].f&&dis[tmp]+e[p].c<dis[e[p].to])
			{
				dis[e[p].to]=dis[tmp]+e[p].c;
				pre[e[p].to]=p;
				if (!inq[e[p].to])
				{
					q.push(e[p].to);
					inq[e[p].to]=true;
				}
			}
		}
	}
	return dis[t]!=INF;
}
int main()
{
	ans=0;
	memset(head,0,sizeof(head));
	F(i,0,249) F(j,0,249) f[i][j]=1;
	scanf("%d%d",&r,&c);
	F(i,0,r-1) 
	{
		F(j,0,c-1)
		{
			ch=getchar();
			while (ch!='L'&&ch!='R'&&ch!='U'&&ch!='D') ch=getchar();
			if (ch=='L'){x=i;y=j-1;}
			if (ch=='R'){x=i;y=j+1;}
			if (ch=='U'){x=i-1;y=j;}
			if (ch=='D'){x=i+1;y=j;}
			x=(x+r)%r;
			y=(y+c)%c;
			f[i*c+j][x*c+y]=0;
			F(k,0,3)
			{
				xx=(i+dx[k]+r)%r;
				yy=(j+dy[k]+c)%c;
				add_edge(i*c+j,xx*c+yy+r*c,1,f[i*c+j][xx*c+yy]);
			}
		}
	}
	s=498;
	t=499;
	F(i,0,r*c-1)
	{
		add_edge(s,i,1,0);
		add_edge(i+r*c,t,1,0);
	}
	while (spfa())
	{
		int mf=INF;
		for(int p=pre[t];p;p=pre[e[p].from]) mf=min(mf,e[p].f);
		ans+=mf*dis[t];
		for(int p=pre[t];p;p=pre[e[p].from])
		{
			e[p].f-=mf;
			e[p^1].f+=mf;
		}
	}
	printf("%d\n",ans);
}