← 返回题目列表

Codeforces · 1689/D

D. 莉娜和矩阵

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

莉娜是一个喜欢逻辑谜题的美丽女孩。

作为生日礼物,莉娜得到了一个矩阵拼图!

矩阵由 $$$n$$$ 行和 $$$m$$$ 列组成,每个单元格为黑色或白色。坐标 $$$(i,j)$$$ 表示每个 $$$1\leq i \leq n$$$ 和 $$$1\leq j \leq m$$$ 属于第 $$$i$$$ 行和 $$$j$$$ 列的单元格。为了解决这个难题,莉娜必须选择一个单元格,该单元格能够最小化与所选单元格最远的黑色单元格的曼哈顿距离。

更正式地说,对于每个 $$$1\leq i \leq k$$$,矩阵中有 $$$k \ge 1$$$ 个黑色单元,坐标为 $$$(x_i,y_i)$$$。 Lena 应该选择一个单元格 $$$(a,b)$$$ 来最小化 $$$$$$\max_{i=1}^{k}(|a-x_i|+|b-y_i|)。$$$$$$

由于莉娜没有技能,她向你求助。你会告诉她选择最佳的细胞吗?

输入

输入数据中有多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10\,000$$$) - 测试用例的数量。接下来是测试用例描述。

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

以下 $$$n$$$ 行每行包含 $$$m$$$ 个字符,每个字符要么是“W”,要么是“B”。如果单元格 $$$(i,j)$$$ 为白色,则这些行中第 $$$i$$$ 中的第 $$$j$$$ 字符为“W”;如果单元格 $$$(i,j)$$$ 为黑色,则第 $$$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$$$。