ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

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

内存限制：256 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：8 通过：2
提交提交记录统计Web Board

题目描述

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

海蒂知道巢穴罐被表示为格子上的矩形，边与轴平行。多边形的每个顶点在格子上占据一个整数点。对于晶格的每个细胞，海蒂可以检查僵尸的污染程度。这是一个介于 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） 的单元格。
输出

输出的第一行应包含 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，检查即可;

The zombies are gathering in their secret lair! Heidi will strike hard to destroy them once and for all. But there is a little problem... Before she can strike, she needs to know where the lair is. And the intel she has is not very good.
Heidi knows that the lair can be represented as a rectangle on a lattice, with sides parallel to the axes. Each vertex of the polygon occupies an integer point on the lattice. For each cell of the lattice, Heidi can check the level of Zombie Contamination. This level is an integer between 0 and 4, equal to the number of corners of the cell that are inside or on the border of the rectangle.
As a test, Heidi wants to check that her Zombie Contamination level checker works. Given the output of the checker, Heidi wants to know whether it could have been produced by a single non-zero area rectangular-shaped lair (with axis-parallel sides). 
Input
The first line of each test case contains one integer N, the size of the lattice grid (5≤N≤50). The next N lines each contain N characters, describing the level of Zombie Contamination of each cell in the lattice. Every character of every line is a digit between 0 and 4.
Cells are given in the same order as they are shown in the picture above: rows go in the decreasing value of y coordinate, and in one row cells go in the order of increasing x coordinate. This means that the first row corresponds to cells with coordinates (1,N),...,(N,N) and the last row corresponds to cells with coordinates (1,1),...,(N,1).
Output
The first line of the output should contain Yes if there exists a single non-zero area rectangular lair with corners on the grid for which checking the levels of Zombie Contamination gives the results given in the input, and No otherwise.
Example
Input 
6
000000
000000
012100
024200
012100
000000
Output 
Yes
Note
The lair, if it exists, has to be rectangular (that is, have corners at some grid points with coordinates (x1,y1), (x1,y2), (x2,y1), (x2,y2)), has a non-zero area and be contained inside of the grid (that is, 0≤x1<x2≤N, 0≤y1<y2≤N), and result in the levels of Zombie Contamination as reported in the input.

输入格式


	所有测试用例的第一行包含一个整数 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，检查即可;




	





        

    

          

      

        

        分类标签