← 返回题目列表

Codeforces · 1592/F1

F1. 爱丽丝和重新着色 1

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

版本之间的差异在于运营成本。一个版本的解决方案不适用于另一个版本!

Alice 有一个大小为 $$$n \times m$$$ 的网格,最初它的所有单元格都是白色的。第 $$$i$$$ 行与第 $$$j$$$ 列交叉处的单元格表示为 $$$(i, j)$$$。 Alice 可以使用这个网格执行以下操作:

- 选择任何包含单元格 $$$(1, 1)$$$ 的子矩形,并翻转其所有单元格的颜色。 (翻转意味着将其颜色从白色变为黑色或从黑色变为白色)。此操作花费 $$$1$$$ 硬币。
- 选择任何包含单元格 $$$(n, 1)$$$ 的子矩形,并翻转其所有单元格的颜色。此操作需要花费 $$$2$$$ 硬币。
- 选择任何包含单元格 $$$(1, m)$$$ 的子矩形,并翻转其所有单元格的颜色。此操作需要花费 $$$4$$$ 硬币。
- 选择任何包含单元格 $$$(n, m)$$$ 的子矩形,并翻转其所有单元格的颜色。此操作需要花费 $$$3$$$ 硬币。

提醒一下,子矩形是所有单元格 $$$(x, y)$$$ 的集合,其中 $$$x_1 \le x \le x_2$$$, $$$y_1 \le y \le y_2$$$ 对于某些 $$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le米$$$。

Alice想通过这些操作获得她最喜欢的颜色。她最少需要花费多少枚硬币?可以证明,始终可以将初始网格转换为任何其他网格。

输入

输入的第一行包含 $$$2$$$ 整数 $$$n, m$$$ ($$$1 \le n, m \le 500$$$) — 网格的尺寸。

接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含长度为 $$$m$$$ 的字符串 $$$s_i$$$,由字母 W 和 B 组成。如果单元格 $$$(i, j)$$$ 的颜色为 Alice 最喜欢的白色,则字符串 $$$j$$$ 的第 $$$j$$$ 字符为 W,如果为彩色,则为 B黑色。

输出

输出爱丽丝为获得她最喜欢的颜色而必须花费的最小数量的硬币。

示例

输入 #1

3 3
WWW
WBB
WBB

输出 #1

3

输入 #2

10 15
WWWBBBWBBBBBWWW
BBBBWWWBBWWWBBB
BBBWWBWBBBWWWBB
BBWBWBBWWWBBWBW
BBBBWWWBBBWWWBB
BWBBWWBBBBBBWWW
WBWWBBBBWWBBBWW
WWBWWWWBBWWBWWW
BWBWWBWWWWWWBWB
BBBWBWBWBBBWWBW

输出 #2

74

注意

在第一个示例中,最好只对包含单元格 $$$(2, 2), (2, 3), (3, 2), (3, 3)$$$ 的矩形应用一次第四次操作。这将花费 $$$3$$$ 硬币。