#P18957. [SEUSA2026] A. 递归图案(Recursive Pattern)
[SEUSA2026] A. 递归图案(Recursive Pattern)
递归图案(Recursive Pattern)
题目描述
一个最简单的递归图案是任意一个 方阵,每个格子是 X 或小写字母 o。

图 A.1:一个基本递归图案。
你可以对已有图案进行扩展:任选一个新的 方阵,把已有图案中的每个 X 替换为这个新方阵,把每个 o 替换为全是 o 的 方阵。扩展后,图案的行数和列数都翻倍。

图 A.2:用左侧的 方阵替换已有图案中的每个 X;已有的 o 被替换为全 o 的方阵,得到右侧的 图案。
可以扩展任意多次。每次选择的 方阵可以不同,但同一次扩展对所有 X 使用相同的方阵。
给定一个由 X、o 组成的矩形网格,判断它是否能作为某个递归图案中的一个连续子矩形。子矩形的位置不必与任一层的分块边界对齐。
输入格式
第一行两个正整数 ,满足 。
随后 行,每行 个字符,只包含 X 和 o。
输出格式
若存在符合要求的递归图案,输出 1;否则输出 0。
样例
2 2
XX
Xo
1
2 3
oXo
Xoo
1
6 45
ooXXXooXooXXXXooooXXXooXXXooXoooXoXXXXoXooXoo
ooXooXoXoXXooooooXXoooXooXXoXoooXooXoooXooXoo
ooXXXooXoXooooooooXoooXoooXoXoooXooXoooXooXoo
ooXoXXoXoXooXXoooooXooXoooXoXoooXooXoooXXXXoo
ooXooXoXoXXooXoooooXXoXooXXoXXooXooXoooXooXoo
ooXXXooXooXXXXoooXXXoooXXXoooXXXoooXoooXooXoo
0
来源
2026 ICPC Southeast USA Regional Programming Contest Division 1,题目 A。