← 返回题目列表

Codeforces · 690/B1

B1. 恢复多边形(简单)

中文机器翻译题面 查看原题

僵尸正在他们的秘密巢穴中聚集!海蒂将全力出击,彻底消灭他们。但有一个小问题……在她发动攻击之前,她需要知道巢穴在哪里。而且她掌握的情报也不是很好。

海蒂知道巢穴可以表示为格子上的矩形,其边平行于轴。多边形的每个顶点占据晶格上的一个整数点。对于格子的每个单元格,海蒂都可以检查僵尸污染的程度。该级别是 0 到 4 之间的整数,等于矩形内部或边界上的单元格的角数。

作为测试,海蒂想要检查她的僵尸污染级别检查器是否有效。给定检查器的输出,海蒂想知道它是否可以由单个非零面积矩形巢穴(具有与轴平行的边)产生。

输入

每个测试用例的第一行包含一个整数N,即格子网格的大小(5 ≤ N ≤ 50)。接下来的 N 行每行包含 N 个字符,描述格子中每个单元格的僵尸污染级别。每行的每个字符都是 0 到 4 之间的数字。

单元格的排列顺序与上图所示的顺序相同:行按照 y 坐标值递减的顺序排列,在一行中单元格按照 x 坐标递增的顺序排列。这意味着第一行对应于坐标为 (1, N), ..., (N, N) 的单元格,最后一行对应于坐标为 (1, 1), ..., (N, 1) 的单元格。

输出

如果网格上存在带有角点的单个非零区域矩形巢穴(检查僵尸污染水平会给出输入中给出的结果),则输出的第一行应包含“是”,否则应包含“否”。

示例

输入 #1

6
000000
000000
012100
024200
012100
000000

输出 #1

Yes

注意

巢穴,如果存在,必须是矩形的(即,在坐标为 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 的某些网格点处有角点),具有非零区域并包含在网格内部(即 0 ≤ x1 < x2 ≤ N,0 ≤ y1 < y2 ≤ N),并得出输入中报告的僵尸污染水平。