CF1689D Lena and Matrix

Lena 是一个喜欢逻辑谜题的漂亮女孩。 在生日时，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'，如果是黑色，则为 'B'。 保证至少存在一个黑色格子。 保证所有测试数据中 $n\cdot m$ 的总和不超过 $10^6$。

对于每组测试数据，输出一个最优的格子 $(a,b)$。如果有多个答案，输出任意一个即可。

在第一个测试用例中，两个黑色格子的坐标分别为 $(1,1)$ 和 $(3,2)$。四个最优的格子是 $(1,2)$、$(2,1)$、$(2,2)$ 和 $(3,1)$。可以证明没有其他格子能使到所有黑色格子的最大曼哈顿距离更小。 在第二个测试用例中，最优选择是黑色格子 $(2,2)$，此时最大曼哈顿距离为 $2$。 由 ChatGPT 4.1 翻译