← 返回题目列表

AtCoder · pakencamp_2020_day2_b

B. 步行

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

配点 : 300 点

問題文

Pakencho位于北部和南部。 H+1 街区,从东到西 W+1 它就像一个块网格。 从北方 i 行,从西边 j 列中的块 由(i,j) 代表。 住在
(1,1) 的美雪决定有一天去散步。 他是 (i,j) (1 \leq i \leq H,1 \leq j \leq W) 于 E 或 S 字符 写入 C_{ij} , 我决定从 (1,1) 开始,按照以下规则散步。 当你在

現在 (x,y) 时, 在

  • x \leq H 和 y \leq W 的情况下,C_{xy} = E 然后向东走,C_{xy}= S 然后向南走。 如果
  • x = H+1 或 y=W+1 ,则步行结束。

我发现了这个计划。 住在 (H,W+1) 的辉夜希望他在散步后去看她,所以她决定重写写在积木上的一些字母。 具体来说, 如果写成E 如果写成 S , 将其重写为S 如果写成 E 。

美雪你的散步 以 (H,W+1) 结尾需要重写的最少字符数是多少?

制約

  • 所有输入均为整数。
  • 1 \leq H,W \leq 2000
  • C_{ij}为 E 或 S

小課題

  1. (5 点) H=1,W=1
  2. (15 点) H=1
  3. (80 点) H=2
  4. (200 点)没有额外的限制。

入力

输入将以以下格式从标准输入给出。

H \ \ W
C_{11} \ldots C_{1W}
\vdots
C_{H1} \ldots C_{HW}

出力

将答案打印到标准输出。


入力例 1

1 1
S

出力例 1

1

如果再这样下去,我就不能散步了。 因为它以 (2,1) 结尾, 将其设置为(1,1) 中写入的字符 E 。
此输入满足子任务 1 和 2 的约束。 这可以通过设置

入力例 2

1 2
ES

出力例 2

1

(1,2) 中写入的字符 E 来实现。
该输入满足子任务 2 的约束。 这可以通过重写

入力例 3

2 3
EEE
SSS

出力例 3

2

(1,3) , (2,3) 中写入的每个字符来实现。
此输入满足子任务 3 的约束。

入力例 4

10 10
SEESESESES
EEESESEEES
EESESEESES
EESSSSESES
SEESSEEEEE
EESESEEESS
EEEESSEEEE
SESESESSES
SEESSEESSE
EESSSSSESS

出力例 4

3

该输入满足子任务 4 的约束。

作者: 定义