Lena and Matrix

题意翻译

$t$ 组数据，每组给定一个由字符 `W` 或 `B` 组成的 $n\times m$ 的矩阵。求这样一个点的坐标，满足其到图中任何一个 `B` 的最大曼哈顿距离最小。 若有多解，可任意输出一个。 $1\le t\le 10000,2\le n,m\le 1000,\sum nm\le 10^6$

题目描述

Lena is a beautiful girl who likes logical puzzles. As a gift for her birthday, Lena got a matrix puzzle! The matrix consists of $ n $ rows and $ m $ columns, and each cell is either black or white. The coordinates $ (i,j) $ denote the cell which belongs to the $ i $ -th row and $ j $ -th column for every $ 1\leq i \leq n $ and $ 1\leq j \leq m $ . To solve the puzzle, Lena has to choose a cell that minimizes the Manhattan distance to the farthest black cell from the chosen cell. More formally, let there be $ k \ge 1 $ black cells in the matrix with coordinates $ (x_i,y_i) $ for every $ 1\leq i \leq k $ . Lena should choose a cell $ (a,b) $ that minimizes $$\max_{i=1}^{k}(|a-x_i|+|b-y_i|). $$ As Lena has no skill, she asked you for help. Will you tell her the optimal cell to choose?

输入输出格式

输入格式

There are several test cases in the input data. The first line contains a single integer $ t $ ( $ 1\leq t\leq 10\,000 $ ) — the number of test cases. This is followed by the test cases description. The first line of each test case contains two integers $ n $ and $ m $ ( $ 2\leq n,m \leq 1000 $ ) — the dimensions of the matrix. The following $ n $ lines contain $ m $ characters each, each character is either 'W' or 'B'. The $ j $ -th character in the $ i $ -th of these lines is 'W' if the cell $ (i,j) $ is white, and 'B' if the cell $ (i,j) $ is black. It is guaranteed that at least one black cell exists. It is guaranteed that the sum of $ n\cdot m $ does not exceed $ 10^6 $ .

输出格式

For each test case, output the optimal cell $ (a,b) $ to choose. If multiple answers exist, output any.

输入输出样例

输入样例 #1

5
3 2
BW
WW
WB
3 3
WWB
WBW
BWW
2 3
BBB
BBB
5 5
BWBWB
WBWBW
BWBWB
WBWBW
BWBWB
9 9
WWWWWWWWW
WWWWWWWWW
BWWWWWWWW
WWWWWWWWW
WWWWBWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWB

输出样例 #1

2 1
2 2
1 2
3 3
6 5

说明

In the first test case the two black cells have coordinates $ (1,1) $ and $ (3,2) $ . The four optimal cells are $ (1,2) $ , $ (2,1) $ , $ (2,2) $ and $ (3,1) $ . It can be shown that no other cell minimizes the maximum Manhattan distance to every black cell. In the second test case it is optimal to choose the black cell $ (2,2) $ with maximum Manhattan distance being $ 2 $ .

**Lena和矩阵**

**题意翻译：**
有 $t$ 组数据，每组数据是一个由字符 `W` 或 `B` 组成的 $n\times m$ 的矩阵。需要找到一个点，使得该点到矩阵中任何一个 `B` 的最大曼哈顿距离最小。如果有多个这样的点，可以输出其中任意一个。数据范围：$1\le t\le 10000,2\le n,m\le 1000,\sum nm\le 10^6$。

**题目描述：**
Lena是一个喜欢逻辑拼图的漂亮女孩。她得到了一个矩阵拼图作为生日礼物。这个矩阵有 $n$ 行和 $m$ 列，每个单元格要么是黑色要么是白色。坐标 $(i,j)$ 表示属于第 $i$ 行和第 $j$ 列的单元格，对于每一个 $1\leq i \leq n$ 和 $1\leq j \leq m$。为了解决这个拼图，Lena需要选择一个单元格，使其到最远的黑色单元格的曼哈顿距离最小。

更正式地说，假设矩阵中有 $k \ge 1$ 个黑色单元格，它们的坐标是 $(x_i,y_i)$，对于每一个 $1\leq i \leq k$。Lena应该选择一个单元格 $(a,b)$，使得

$$\max_{i=1}^{k}(|a-x_i|+|b-y_i|)$$

尽可能小。由于Lena没有解决这个问题的技能，她请求你的帮助。你能告诉她应该选择哪个单元格吗？

**输入输出格式：**
**输入格式：**
输入数据包含多个测试用例。第一行包含一个整数 $t$ ($1\leq t\leq 10,000$) —— 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2\leq n,m \leq 1000$) —— 矩阵的维度。

接下来的 $n$ 行每行包含 $m$ 个字符，每个字符要么是 `W` 要么是 `B`。这些行的第 $i$ 行的第 $j$ 个字符如果是 `W`，则表示单元格 $(i,j)$ 是白色的，如果是 `B`，则表示是黑色的。

保证至少存在一个黑色单元格。

保证 $n\cdot m$ 的总和不超过 $10^6$。

**输出格式：**
对于每个测试用例，输出最佳选择的单元格 $(a,b)$。如果存在多个答案，输出其中任意一个。

**输入输出样例：**
**输入样例 #1：**
```
5
3 2
BW
WW
WB
3 3
WWB
WBW
BWW
2 3
BBB
BBB
5 5
BWBWB
WBWBW
BWBWB
WBWBW
BWBWB
9 9
WWWWWWWWW
WWWWWWWWW
BWWWWWWWW
WWWWWWWWW
WWWWBWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWB
```
**输出样例 #1：**
```
2 1
2 2
1 2
3 3
6 5
```

**说明：**
在第一个测试用例中，两个黑色单元格的坐标是 $(1,1)$ 和 $(3,2)$。四个最佳单元格是 $(1,2)$, $(2,1)$, $(2,2)$ 和 $(3,1)$。可以证明没有其他单元格能够使得到每个黑色单元格的最大曼哈顿距离最小。

在第二个测试用例中，选择黑色单元格 $(2,2)$ 是最优的，其到最远黑色单元格的曼哈顿距离为 $2$。**Lena和矩阵** **题意翻译：** 有 $t$ 组数据，每组数据是一个由字符 `W` 或 `B` 组成的 $n\times m$ 的矩阵。需要找到一个点，使得该点到矩阵中任何一个 `B` 的最大曼哈顿距离最小。如果有多个这样的点，可以输出其中任意一个。数据范围：$1\le t\le 10000,2\le n,m\le 1000,\sum nm\le 10^6$。 **题目描述：** Lena是一个喜欢逻辑拼图的漂亮女孩。她得到了一个矩阵拼图作为生日礼物。这个矩阵有 $n$ 行和 $m$ 列，每个单元格要么是黑色要么是白色。坐标 $(i,j)$ 表示属于第 $i$ 行和第 $j$ 列的单元格，对于每一个 $1\leq i \leq n$ 和 $1\leq j \leq m$。为了解决这个拼图，Lena需要选择一个单元格，使其到最远的黑色单元格的曼哈顿距离最小。 更正式地说，假设矩阵中有 $k \ge 1$ 个黑色单元格，它们的坐标是 $(x_i,y_i)$，对于每一个 $1\leq i \leq k$。Lena应该选择一个单元格 $(a,b)$，使得 $$\max_{i=1}^{k}(|a-x_i|+|b-y_i|)$$ 尽可能小。由于Lena没有解决这个问题的技能，她请求你的帮助。你能告诉她应该选择哪个单元格吗？ **输入输出格式：** **输入格式：** 输入数据包含多个测试用例。第一行包含一个整数 $t$ ($1\leq t\leq 10,000$) —— 测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2\leq n,m \leq 1000$) —— 矩阵的维度。 接下来的 $n$ 行每行包含 $m$ 个字符，每个字符要么是 `W` 要么是 `B`。这些行的第 $i$ 行的第 $j$ 个字符如果是 `W`，则表示单元格 $(i,j)$ 是白色的，如果是 `B`，则表示是黑色的。 保证至少存在一个黑色单元格。 保证 $n\cdot m$ 的总和不超过 $10^6$。 **输出格式：** 对于每个测试用例，输出最佳选择的单元格 $(a,b)$。如果存在多个答案，输出其中任意一个。 **输入输出样例：** **输入样例 #1：** ``` 5 3 2 BW WW WB 3 3 WWB WBW BWW 2 3 BBB BBB 5 5 BWBWB WBWBW BWBWB WBWBW BWBWB 9 9 WWWWWWWWW WWWWWWWWW BWWWWWWWW WWWWWWWWW WWWWBWWWW WWWWWWWWW WWWWWWWWW WWWWWWWWW WWWWWWWWB ``` **输出样例 #1：** ``` 2 1 2 2 1 2 3 3 6 5 ``` **说明：** 在第一个测试用例中，两个黑色单元格的坐标是 $(1,1)$ 和 $(3,2)$。四个最佳单元格是 $(1,2)$, $(2,1)$, $(2,2)$ 和 $(3,1)$。可以证明没有其他单元格能够使得到每个黑色单元格的最大曼哈顿距离最小。 在第二个测试用例中，选择黑色单元格 $(2,2)$ 是最优的，其到最远黑色单元格的曼哈顿距离为 $2$。