← 返回题目列表

Codeforces · 1627/A

A. 不着色

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

有一个包含 $$$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$$$ 中的单元格将变为黑色。