配点 : 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
小課題
- (5 点) H=1,W=1
- (15 点) H=1
- (80 点) H=2
- (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 的约束。
作者: 定义