粉刷

题目描述

小爱是一位粉刷匠，她现在需要粉刷一块包含 $n \times m$ 小格子的墙面，每个格子一开始都是白色的。小爱可以进行以下两种操作：

• 把某一行全部染成红色 R 或者黑色 B。
• 把某一列全部染成红色 R 或者黑色 B。

每次涂到一个格子时，无论这个格子之前是否被染过色，都会被覆盖成当前的颜色。经过一些操作后，小爱制作完成了一个只有红色与黑色的染色图。给出一幅染色图，输出最少需要几步可以画成这幅图。如果无法通过以上操作获得，则输出 $-1$。

输入格式

第一行两个正整数 $n, m$，分别表示染色图的长和宽。 接下来 $n$ 行，每行一个长度为 $m$ 且只由 R、B 构成的字符串，用来描述整幅染色图。

输出格式

输出一个正整数表示答案。

样例输入 #1

2 8
BBRRRBRB
BBRRRRRB

样例输出 #1

6

样例输入 #2

2 3
RRB
BRR

样例输出 #2

-1

数据范围

• 对于 $20\%$ 的数据，$1 \leq n, m \leq 3$；
• 对于 $40\%$ 的数据，$1 \leq n, m \leq 5$；
• 对于 $60\%$ 的数据，$1 \leq n, m \leq 100$；
• 对于 $100\%$ 的数据，$1 \leq n, m \leq 3000$。

知识点与难度

本题涉及的知识点从属于 GESP 六级（贪心、哈希、排序），难度等级：⭐⭐⭐⭐。

测试点分布