版本之间的差异在于运营成本。一个版本的解决方案不适用于另一个版本!
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$$$ 硬币。