C1183 [Contest #1]牛吃草问题 +1

内存限制:256 MB 时间限制:1000 ms

题目描述

AA 家里养了一头老黑牛,并且在后院里种了几株草。更精确的说,若把后院视为平面坐标系,并给定两个正整数 $N, M$,那么在所有满足 $1 \le i \le N$ 和 $1 \le j \le M$ 的整数坐标位置 $(i, j)$ 都种了一株草。

现在 AA 用一条伸缩能力为 $r$ 的绳子把老黑牛绑在坐标 $(x, y)$ 的位置 ($r$ 是非负整数, $x, y$ 必须是整数,但 $x, y$ 可能小于 $1$ 或分别大于 $N, M$)。这条绳子很奇特,可以让老黑牛吃到所有坐标在 $(i, j)$ 且满足 $|x - i| + |y - j| \le r$ 的草。

再次强调,和本場比賽的A題-牛吃草问题中的老黄牛并不一样,AA 绑老黑牛的位置没有其他的限制,也就是说,$x, y$ 甚至可能小于 $1$ 或分别大于 $N, M$。

老黑牛非常贪吃,会把所有能吃到的草啃食殆尽,现在给你 AA 家后院被老黑牛啃食完毕的景况,也就是每个坐标 $(i, j)$ 的草是否被吃掉。请回答 AA 所使用的绳子的伸缩能力为多少,以及老黑牛被绑的位置坐标。

若有多组可能解,请输出绳子伸缩能力 $r$ 最小的解,若仍有多组可能解,请输出 $x$ 座标最小的解,若仍有多组解,请输出 $y$ 坐标最小的解。

另外,为了排除解释起来有点麻烦的状况,数据保证至少有一个位置的草被老黑牛吃掉。

若无解的话,则把 $r,x,y$ 都當作 $-1$ 輸出。

输入格式

第一行有一个正整数 $T$ ($T \le 10^5$),代表有几组数据。

接着每个数据的第一行有两个正整数 $N, M$ ($1 \le N, M \le 1000$) 代表 AA 家后院有种草的坐标范围。接着还有 $N$ 行,每行有一个长度为$M$ 且由 '#' 和 '.' 两种字符组成的字符串,若当中的第 $i$ 个字符串的第 $j$ 个字符为 '#',代表坐标在 $(i, j)$ 的草没被老黑牛吃掉;相对的,若为 '.',则代表该坐标的草被老黑牛吃掉了。

每个数据至少包含一个 '.' 字符。

每组数据的 $N \times M$ 之和不超过 $10^6$。

输出

对于每组数据,输出一行包含三个整数 $r,x,y$ 代表答案($r,x,y$ 的意义参照题目描述)。

样例

样例输入 1

3 2 4 ##.# #... 4 3 ..# .## ##. #.. 4 4 ...# .... .... ....

样例输出 1

1 2 3 -1 -1 -1 3 3 2

提示