AT_pakencamp_2020_day2_b Walking

パ研町是一个被划分为 $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`。Miyuki 打算从 $(1, 1)$ 出发，按照以下规则进行散步： - 对于当前位置 $(x, y)$， - 如果 $x \leq H$ 且 $y \leq W$，如果 $C_{xy} = \text{E}$，则向东走；如果 $C_{xy} = \text{S}$，则向南走。 - 如果 $x = H + 1$ 或 $y = W + 1$，则散步结束。 住在 $(H, W + 1)$ 的 Kaguya 想让 Miyuki 在散步结束后顺便来拜访她。因此，她想修改一些格子中的字符：如果某格子中原本为 `E`，她可以改为 `S`；如果是 `S`，她可以改为 `E`。 为了让 Miyuki 的散步在 $(H, W + 1)$ 结束，Kaguya 至少需要修改多少个字符？

输入包含如下格式的数据： > $H\ W$ > $C_{11}\ \ldots\ C_{1W}$ > $\vdots$ > $C_{H1}\ \ldots\ C_{HW}$

输出一个整数，表示最少需要修改的字符个数。

- 所有输入均为整数。 - $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 分）无其他限制 ### 示例解释 - 示例1：不修改的话，Miyuki 会在 $(2, 1)$ 结束。需要将 $(1, 1)$ 的字符改为 `E`。该输入满足子任务 1 和 2 的条件。 - 示例2：只需将 $(1, 2)$ 上的字符改为 `E` 即可。该输入满足子任务 2 的条件。 - 示例3：修改 $(1, 3)$ 和 $(2, 3)$ 的字符即可达到目标。该输入满足子任务 3 的条件。 - 示例4：该输入满足子任务 4 的条件。 **本翻译由 AI 自动生成**