问题 6639 --曼哈顿圆

6639: 曼哈顿圆★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 20  解决: 11
[提交][状态][命题人:]

题目描述

       给定一个大小为n × m,由‘.''#'字符填充的网格,网格的左上角坐标为(1,1),右下角坐标为(n,m)。在网格上存在一个完整的曼哈顿圆。

规定:如果|ha|+|kb|<rr为正的常数),点(a,b)属于以(h,k)为中心的曼哈顿圆,作为曼哈顿圆这部分的点集都为‘#‘。请输出该曼哈顿圆的圆心坐标。

输入

第一行包含一个整数t(1t1000)——测试用例的数量。

对于每个测试用例:

第一行为两个整数nm1<=n*m<=2e5,分别为网格的高度和宽度;

接下来共有n行,每行m个字符,由‘.’和‘#’两种字符组成;

测试数据确保,所有测试数据的n*m之和不超过2e5;

输出

对于每个测试用例,输出一行两个整数,为曼哈顿圆的圆心坐标;

样例输入
Copy
6
5 5
.....
.....
..#..
.....
.....
5 5
..#..
.###.
#####
.###.
..#..
5 6
......
......
.#....
###...
.#....
1 1
#
5 6
...#..
..###.
.#####
..###.
...#..
2 10
..........
...#......
样例输出
Copy
3 3
3 3
4 2
1 1
3 4
2 4

提示

来源

 

[提交][状态]