僵尸们正在他们的秘密巢穴中聚集!海蒂会一劳永逸地打击他们。但是有一个小问题...在她出手之前,她需要知道巢穴在哪里。而且她拥有的英特尔不是很好。
海蒂知道巢穴罐被表示为格子上的矩形,边与轴平行。多边形的每个顶点在格子上占据一个整数点。对于晶格的每个细胞,海蒂可以检查僵尸的污染程度。这是一个介于 0 和 4 之间的整数,等于矩形 Bor Der 内部或上的单元格的角数。
作为测试,海蒂想检查她僵尸污染水平检查器是否有效。给定检查器的输出,Heidi 想知道它是否可以由单个非零面积 rec 切向形巢穴(轴平行边)产生。
输入
所有测试用例的第一行包含一个整数 n,即格栅的大小 (5≤ N ≤5 0)。接下来的n行各包含n个字符,描述了晶格中E Ach细胞的僵尸污染程度。每行的每个字符都是 0 到 4 之间的数字。
单元格的给出顺序与上图所示的顺序相同:行按 y 坐标的递减值排列,在一行中,单元格按 x 坐标递增的顺序排列。这意味着第一行对应于坐标为 (1, n), ..., (n, n) 的单元格,最后一行对应于坐标为 (1, 1), ..., (N, 1) 的单元格。
如果存在,必须是矩形的(也就是说,在一些网格点上有角,坐标为(x 1,y 1),< span类= “Tex-span” > ( x 1, y 2), ( x 2, y 1), ( x 2, y 2),具有非零区域并 包含在网格内(即0≤ x 1 & Lt x 2≤ N, 0≤ y 1 < y 2≤ N ),并导致输入中报告的僵尸污染水平。
分析:四角为1,边缘为2,内部为4,检查即可;
所有测试用例的第一行包含一个整数 n,即格栅的大小 (5≤ N ≤5 0)。接下来的n行各包含n个字符,描述了晶格中E Ach细胞的僵尸污染程度。每行的每个字符都是 0 到 4 之间的数字。
单元格的给出顺序与上图所示的顺序相同:行按 y 坐标的递减值排列,在一行中,单元格按 x 坐标递增的顺序排列。这意味着第一行对应于坐标为 (1, n), ..., (n, n) 的单元格,
最后一行对应于坐标为 (1, 1), ..., (N, 1) 的单元格。
输出的第一行应包含 Yes,如果网格上存在一个带有角落的非零区域矩形巢穴,检查僵尸污染水平会给出输入中给出的结果,并且没有其他 Ise。
6
000000
000000
012100
024200
012100
000000
Yes
巢穴,如果存在,必须是矩形的(也就是说,在一些网格点上有角,坐标为(x 1,y 1),< span类= “Tex-span” > ( x 1, y 2), ( x 2, y 1), ( x 2, y 2),具有非零区域并 包含在网格内(即0≤ x 1 & Lt x 2≤ N, 0≤ y 1 < y 2≤ N ),并导致输入中报告的僵尸污染水平。
分析:四角为1,边缘为2,内部为4,检查即可;