ZOJ Problem Set - 3287
Give a computer doughnut and an apple,would the computer know the difference? Actually, that depends on the inner workings of the computer, whether it has been programmed to be able to do so by a talented programmer as you!
Now, to differentiate two objects involves many aspects, colors, textures, size,shape, and so on. But an intelligent program should be able to differentiate the most essential aspect, structure. Note that a doughnut has a hole through it while an apple doesn't. To simplify, the followings hold:
This all seems confusing, a simple description would be:A doughnut object could have a loop drawn on it's surface that does not separate it into two parts, while an apple object does not.
Now given the description an object, you are to determine if it's a doughnut object or an apple object.
There are many test cases,each are of the form:
First there are three integers representing the dimensions of the input: A(1 <= A <= 5),B(1 <= B <= 5),C(1 <= C <= 5).
Then follows A matrices each with B rows and C columns. 0 stands for not part of the object and 1 stands for part of the object. The object will not be of zero volume.
For each test case, if the object is an apple object, output "APPLE". If it's a doughnut object output "DOUGHNUT".
1 1 1 1 1 3 3 1 1 1 1 0 1 1 1 1
Let P be a polyhedron which satisfies:
(a)Any two vertices of P can be connected by a chian of edges.
(b)Any loop on P which is made up of straight line segments(not necessarily edges) separates P into two pieces.
Then Vertex Number - Edge Number + Face Number = 2 for P.
Author: SONG, Yu
Source: ZOJ Monthly, January 2010