僵尸正在他们的秘密巢穴中聚集!海蒂将全力出击,彻底消灭他们。但有一个小问题……在她发动攻击之前,她需要知道巢穴在哪里。而且她掌握的情报也不是很好。
海蒂知道巢穴可以表示为格子上的矩形,其边平行于轴。多边形的每个顶点占据晶格上的一个整数点。对于格子的每个单元格,海蒂都可以检查僵尸污染的程度。该级别是 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),并得出输入中报告的僵尸污染水平。