309116: CF1627A. Not Shading

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Not Shading

题意翻译

### 题目描述 有一个包含 $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$ 列中的单元格变为黑色所需的最小操作数。

题目描述

There is a grid with $ n $ rows and $ m $ columns. Some cells are colored black, and the rest of the cells are colored white. In one operation, you can select some black cell and do exactly one of the following: - color all cells in its row black, or - color all cells in its column black. You are given two integers $ r $ and $ c $ . Find the minimum number of operations required to make the cell in row $ r $ and column $ c $ black, or determine that it is impossible.

输入输出格式

输入格式


The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains four integers $ n $ , $ m $ , $ r $ , and $ c $ ( $ 1 \leq n, m \leq 50 $ ; $ 1 \leq r \leq n $ ; $ 1 \leq c \leq m $ ) — the number of rows and the number of columns in the grid, and the row and column of the cell you need to turn black, respectively. Then $ n $ lines follow, each containing $ m $ characters. Each of these characters is either 'B' or 'W' — a black and a white cell, respectively.

输出格式


For each test case, if it is impossible to make the cell in row $ r $ and column $ c $ black, output $ -1 $ . Otherwise, output a single integer — the minimum number of operations required to make the cell in row $ r $ and column $ c $ black.

输入输出样例

输入样例 #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

说明

The first test case is pictured below. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1627A/006f296ce37ab26d023536c5e7e41de01691833b.png)We can take the black cell in row $ 1 $ and column $ 2 $ , and make all cells in its row black. Therefore, the cell in row $ 1 $ and column $ 4 $ will become black. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1627A/e018e39d4a3ff2c8dae38c225d35d71cef5b4fe3.png)In the second test case, the cell in row $ 2 $ and column $ 1 $ is already black. In the third test case, it is impossible to make the cell in row $ 2 $ and column $ 2 $ black. The fourth test case is pictured below. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1627A/9cc5664ad8d593a6fe091daeba46d4b798edf4b6.png)We can take the black cell in row $ 2 $ and column $ 2 $ and make its column black. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1627A/5251e98b311c329f4c2934321ce7c0304a9d65c3.png)Then, we can take the black cell in row $ 1 $ and column $ 2 $ and make its row black. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1627A/7c27af972251ec6b51344f07f139aa2dfea8f098.png)Therefore, the cell in row $ 1 $ and column $ 1 $ will become black.

Input

题意翻译

### 题目描述 有一个包含 $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$ 列中的单元格变为黑色所需的最小操作数。

加入题单

上一题 下一题 算法标签: