#P4473. [Jsoi2015]symmetry

    ID: 3707 传统题 1000ms 512MiB 尝试: 71 已通过: 25 难度: 7 上传者: 标签>难度分类提高字符串二维哈希双哈希排序与序列处理二分答案枚举与搜索暴力枚举模拟与实现技巧坐标变换构造与建模对称性分析CF2200By佚名上传

[Jsoi2015]symmetry

[JSOI2015] symmetry

题目描述

张老师用一个 00、11 方阵表示正方形图形。每个单元格对应一个小方格,00 代表白色,11 代表黑色。

正方形的四条候选对称轴是水平中线、竖直中线和两条对角线。若至少有一条轴反射后图形保持不变,就说它是轴对称图形。以下两个图形均为轴对称图形。

100  010
100  101
111  000

以中心顺时针旋转 90∘90^\circ 或 180∘180^\circ 后保持不变,分别称为 90∘90^\circ 对称或 180∘180^\circ 对称。下面左图是 180∘180^\circ 对称,右图是 90∘90^\circ 对称。

0011  1011
1110  1110
0111  0111
1100  1101

若有两条互相垂直的对称轴,称为 44 对称。若关于四条候选轴均对称,称为 88 对称。44 对称等价于同时具有轴对称和 180∘180^\circ 对称,88 对称等价于同时具有轴对称和 90∘90^\circ 对称。

给定一个 n×nn\times n 方阵,分别找出满足这五类对称条件的最大连续子方阵。每个子方阵由连续的若干行和同样多的连续列的交叉区域构成。边长为 11 的方阵满足全部五类条件。

输入格式

第一行输入正整数 nn。

接下来 nn 行,每行输入一个长为 nn 的 00、11 字符串。

输出格式

输出一行五个整数,按 88 对称、90∘90^\circ 对称、44 对称、180∘180^\circ 对称、轴对称的顺序给出最大边长。

样例

5
11100
11000
10111
11000
11100
2 2 3 3 5

样例说明

大方阵关于水平中线对称。左上角有一个 2×22\times2 的 88 对称子方阵,中间三行的最右三列构成一个 44 对称子方阵。

数据范围

5≤n≤5005\le n\le500。