← 返回题目列表

Codeforces · 1985/D

D. 曼哈顿圈

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

给定一个由 $$$m$$$ 组成的 $$$n$$$ 网格,其中包含 '.'和“#”字符,则网格上存在整个曼哈顿圈。网格左上角的坐标为$$$(1,1)$$$,右下角的坐标为$$$(n, m)$$$。

点 ($$$a, b$$$) 属于以 ($$$h, k$$$) 为中心的曼哈顿圆,如果 $$$|h - a| + |k - b| < r$$$,其中 $$$r$$$ 是正常数。

在网格上,属于曼哈顿圆的点集被标记为“#”。找到圆心的坐标。

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \cdot m \leq 2 \cdot 10^5$$$) — 分别是网格的高度和宽度。

接下来的 $$$n$$$ 行包含 $$$m$$$ 个字符“.”或者 '#'。如果字符是“#”,则该点是曼哈顿圆的一部分。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$2 \cdot 10^5$$$,并且网格上有一个完整的曼哈顿圆。

输出

对于每个测试用例,输出两个整数,即圆心的坐标。

示例

输入 #1

6
5 5
.....
.....
..#..
.....
.....
5 5
..#..
.###.
#####
.###.
..#..
5 6
......
......
.#....
###...
.#....
1 1
#
5 6
...#..
..###.
.#####
..###.
...#..
2 10
..........
...#......

输出 #1

3 3
3 3
4 2
1 1
3 4
2 4