对于给定的 的、仅由 和 构成的矩阵中,找到一个边长最大的正方形,使得正方形的四个顶点均为字符 。
输入描述:
第一行输入一个整数 代表矩阵大小。此后 行,每行输入一个长度为 的、仅由 和 构成的字符串代表矩阵。保证输入数据中至少存在一个满足条件的正方形。


输出描述:
输出四行,每行两个整数,代表正方形四个顶点所在的单元格。我们使用 表示网格中从上往下数第 行和从左往右数第 列的单元格,从 开始编号。如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
示例1

输入

8
*####***
*####***
*####***
*#####**
********
***#***#
********
*****#**

输出

1 2
4 2
1 5
4 5

说明

\hspace{15pt}该样例如图所示。特别的,橙色正方形的边长为 2\sqrt2 ,比粉色正方形小。

示例2

输入

8
*#*#****
*****#**
******#*
*#******
#*******
****#***
********
********

输出

1 2
2 6
5 1
6 5

说明

\hspace{15pt}该样例如图所示。橙色正方形的边长为 \sqrt{13} ,粉色正方形的边长为 \sqrt{17}

加载中...