先把题意抽象一下。
给定一个 n×m 的字符矩阵,每个位置是 'B' 或 'S'。
对于每一行,我们可以独立选择删除这一行最左侧的 k 个字符,其中 0≤k≤m。
要求删除后,整个矩阵中剩余的 'B' 和 'S' 数量相等。
目标是让删除的总字符数最少。
有一个大小为 n×m 的储物柜,格子里放着两种果酱:蓝莓酱(记作 ′B′)和草莓酱(记作 ′S′),他希望储物柜中两种果酱的数量相等。
对于储物柜的每一行,你都可以独立地选择移除其最左侧的 k 瓶果酱(0≤k≤m,k=0表示不移除该行的任何果酱)。
请你计算,最少需要拿走多少瓶果酱,才能使柜中剩余的 ′B′与 ′S′的数量相等。
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤2×103)表示测试组数。
对每组测试数据:
保证所有测试组中 ∑(n×m)≤5×103。
对于每组测试数据,输出一行,仅包含一个整数———为使′b′与′S′数量相等所需拿走的最少瓶数
输入
3
1 5
BSSSB
2 4
BSSB
SBBB
2 3
BBB
SSS
输出
3
4
0
说明