← 返回题目列表

Codeforces · 1391/B

B. 修复你

中文机器翻译题面 查看原题

考虑使用由 $$$n$$$ 行和 $$$m$$$ 列组成的网格表示的传送带。从顶部算起第 $$$i$$$ 行和从左侧算起第 $$$j$$$ 列中的单元格标记为 $$$(i,j)$$$。

除了 $$$(n,m)$$$ 之外,每个单元格都分配有方向 R(右)或 D(下)。如果单元格 $$$(i,j)$$$ 指定为 R 方向,则其上保留的任何行李都将移动到单元格 $$$(i,j+1)$$$。类似地,如果单元格 $$$(i,j)$$$ 被分配方向 D,则保留在该单元格上的任何行李都将移动到单元格 $$$(i+1,j)$$$。如果行李在任何时候移出网格,则视为丢失。

$$$(n,m)$$$ 牢房内有一个柜台,所有行李均从这里领取。当且仅当任何行李到达柜台时,无论最初放置在哪个单元,传送带才被称为功能性传送带。更正式地说,对于每个单元 $$$(i,j)$$$,放置在该单元中的任何行李最终都应位于单元 $$$(n,m)$$$ 中。

这最初可能不成立;但是,您可以更改某些单元格的方向以使传送带发挥作用。请确定您必须更改的最小单元格数量。

请注意,始终可以通过更改某些单元组的方向来使任何传送带发挥作用。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n, m$$$ ($$$1 \le n \le 100$$$, $$$1 \le m \le 100$$$) — 分别是行数和列数。

以下 $$$n$$$ 行每行包含 $$$m$$$ 个字符。第 $$$i$$$ 行中的第 $$$j$$$ 个字符 $$$a_{i,j}$$$ 是单元格 $$$(i, j)$$$ 的初始方向。请注意 $$$a_{n,m}=$$$ C.

输出

对于每种情况,在新行中输出为使传送带正常运行而必须更改的最小单元数。

示例

输入 #1

4
3 3
RRD
DDR
RRC
1 4
DDDC
6 9
RDDDDDRRR
RRDDRRDDD
RRDRDRRDR
DDDDRDDRR
DRRDRDDDR
DDRDRRDDC
1 1
C

输出 #1

1
3
9
0

注意

在第一种情况下,只需将 $$$(2,3)$$$ 的方向更改为 D 就足够了。

您可以验证生成的传送带是否正常工作。例如,如果我们将任何行李放置在$$$(2,2)$$$,它首先移动到$$$(3,2)$$$,然后移动到$$$(3,3)$$$。

在第二种情况下,我们别无选择,只能将前 $$$3$$$ 单元格从 D 更改为 R,使网格等于 RRRC。