4673: Recover Polygon (easy) 恢复多边形(简单)

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:9 通过:8

题目描述

僵尸们正在他们的秘密巢穴中聚集!海蒂会一劳永逸地打击他们。但是有一个小问题...在她出手之前,她需要知道巢穴在哪里。而且她拥有的英特尔不是很好。

海蒂知道巢穴罐被表示为格子上的矩形,边与轴平行。多边形的每个顶点在格子上占据一个整数点。对于晶格的每个细胞,海蒂可以检查僵尸的污染程度。这是一个介于 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, 2),具有非零区域并 包含在网格内(即0≤ x 1 & Lt 2≤ N 0≤ y 1 < 2≤ ),并导致输入中报告的僵尸污染水平。

分析:四角为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, 2),具有非零区域并 包含在网格内(即0≤ x 1 & Lt 2≤ N 0≤ y 1 < 2≤ ),并导致输入中报告的僵尸污染水平。

分析:四角为1,边缘为2,内部为4,检查即可;