Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
パ研町は,南北に H+1 ブロック,東西に W+1 ブロックのグリッド状になっている.
北から i 行目,西から j 列目のブロックを(i,j) で表す.
(1,1) に住んでいる Miyuki 君は,ある日散歩をしようと思い立った.
彼は (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) に住む Kaguya さんは,彼に散歩が終わったついでで訪問して欲しいと考え,ブロックに書かれた文字をいくつか書き換える事にした. 具体的には,
E
と書かれていた場合は S
に,S
と書かれていた場合は E
に書き換える.Miyuki 君の散歩が (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 の制約を満たす.
Writer : define