【bzoj3171】[Tjoi2013]循环格

2014年3月18日1,9880

Description

Input

第一行两个整数R,C。表示行和列,接下来R行,每行C个字符LRUD,表示左右上下。

Output

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

Sample Input

3 4
RRRD
URLL
LRRR

Sample Output

2

HINT

1<=R,L<=15

题解

可知每个点的出度=入度=1

二分图+费用流

S向每个点连容量1费用0的边

每个点拆出的点向T连容量1,费用0的边

每个格子向四周连费用0或1的边