有一个包含 $$$n$$$ 行和 $$$m$$$ 列的网格。一些细胞呈黑色,其余细胞呈白色。
在一项操作中,您可以选择一些黑色单元格并执行以下操作之一:
- 将其行中的所有单元格涂成黑色,或者
- 将其列中的所有单元格涂成黑色。
给你两个整数 $$$r$$$ 和 $$$c$$$。求使$$$r$$$ 行、$$$c$$$ 列的单元格变黑所需的最少操作次数,或者确定不可能。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含四个整数 $$$n$$$、$$$m$$$、$$$r$$$ 和 $$$c$$$ ($$$1 \leq n, m \leq 50$$$; $$$1 \leq r \leq n$$$; $$$1 \leq c \leq m$$$) — 行数和行数网格中的列,以及需要分别变黑的单元格的行和列。
接下来是 $$$n$$$ 行,每行包含 $$$m$$$ 个字符。这些字符中的每一个都是“B”或“W”——分别是黑色和白色单元格。
输出
对于每个测试用例,如果无法使$$$r$$$行和$$$c$$$列中的单元格变为黑色,则输出$$$-1$$$。
否则,输出一个整数 - 使 $$$r$$$ 行和 $$$c$$$ 列中的单元格变黑所需的最少操作数。
示例
输入 #1
9 3 5 1 4 WBWWW BBBWB WWBBB 4 3 2 1 BWW BBW WBB WWB 2 3 2 2 WWW WWW 2 2 1 1 WW WB 5 9 5 9 WWWWWWWWW WBWBWBBBW WBBBWWBWW WBWBWBBBW WWWWWWWWW 1 1 1 1 B 1 1 1 1 W 1 2 1 1 WB 2 1 1 1 W B
输出 #1
1 0 -1 2 2 0 -1 1 1
注意
第一个测试用例如下图所示。
我们可以取$$$1$$$行和$$$2$$$列中的黑色单元格,并将其行中的所有单元格设置为黑色。因此,行 $$$1$$$ 和列 $$$4$$$ 中的单元格将变为黑色。
在第二个测试用例中,行 $$$2$$$ 和列 $$$1$$$ 中的单元格已经是黑色的。
在第三个测试用例中,不可能将 $$$2$$$ 行和 $$$2$$$ 列中的单元格设置为黑色。
第四个测试用例如下图所示。
我们可以将 $$$2$$$ 行和 $$$2$$$ 列中的黑色单元格设为黑色。
然后,我们可以将$$$1$$$行和$$$2$$$列中的黑色单元格设为黑色。
因此,行 $$$1$$$ 和列 $$$1$$$ 中的单元格将变为黑色。