logo AlgoBeat OnlineJudge
登录 注册

#103171. [BZOJ 3171] [Tjoi2013]循环格

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

一个循环格就是一个矩阵,其中所有元素为箭头,指向相邻四个格子。每个元素有一个坐标(行,列),其中左上角元素坐标为 。给定一个起始位置 ,你可以沿着箭头防线在格子间行走。即如果 是一个左箭头,那么走到 ;如果是右箭头那么走到 ;如果是上箭头那么走到 ;如果是下箭头那么走到 ;每一行和每一列都是循环的,即如果走出边界,你会出现在另一侧。

一个完美的循环格是这样定义的:对于任意一个起始位置,你都可以沿着箭头最终回到起始位置。如果一个循环格不满足完美,你可以随意修改任意一个元素的箭头直到完美。给定一个循环格,你需要计算最少需要修改多少个元素使其完美。

输入格式

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

输出格式

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

样例

样例输入 #1

4 4
RRRD
URDD
UULD
ULLL

样例输出 #1

0

样例输入 #2

3 4
RRRD
URLL
LRRR

样例输出 #2

2

数据范围与提示