uva1103

maksyuki 发表于 oj 分类，标签:
31 5月 2018
0

In order to understand early civilizations, archaeologists often study texts written in ancient languages. One such language, used in Egypt more than 3000 years ago, is based on characters called hieroglyphs. In this problem, you will write a program to recognize these six characters.

Input

The input consists of several test cases, each of which describes an image containing one or more hieroglyphs chosen from among those shown in Figure C.1. The image is given in the form of a series of horizontal scan lines consisting of black pixels (represented by 1) and white pixels (represented by 0). In the input data, each scan line is encoded in hexadecimal notation. For example, the sequence of eight pixels 10011100 (one black pixel, followed by two white pixels, and so on) would be represented in hexadecimal notation as 9c. Only digits and lowercase letters a through f are used in the hexadecimal encoding. The first line of each test case contains two integers, H and W. H (0 < H ≤ 200) is the number of scan lines in the image. W (0 < W ≤ 50) is the number of hexadecimal characters in each line. The next H lines contain the hexadecimal characters of the image, working from top to bottom. Input images conform to the following rules:

• The image contains only hieroglyphs shown in Figure C.1.

• Each image contains at least one valid hieroglyph.

• Each black pixel in the image is part of a valid hieroglyph.

• Each hieroglyph consists of a connected set of black pixels and each black pixel has at least one other black pixel on its top, bottom, left, or right side.

• The hieroglyphs do not touch and no hieroglyph is inside another hieroglyph.

• Two black pixels that touch diagonally will always have a common touching black pixel.

• The hieroglyphs may be distorted but each has a shape that is topologically equivalent to one of the symbols in Figure C.1. (Two figures are topologically equivalent if each can be transformed into the other by stretching without tearing.)

The last test case is followed by a line containing two zeros.

Output

For each test case, display its case number followed by a string containing one character for each hieroglyph recognized in the image, using the following code:

Ankh: A

Wedjat: J

Djed: D

Scarab: S

Was: W

Akhet: K

In each output string, print the codes in alphabetic order. Follow the format of the sample output. The sample input contains descriptions of test cases shown in Figures C.2 and C.3. Due to space constraints not all of the sample input can be shown on this page.

Sample Input

100 25
0000000000000000000000000
0000000000000000000000000
...(50 lines omitted)...
00001fe0000000000007c0000
00003fe0000000000007c0000
...(44 lines omitted)...
0000000000000000000000000
0000000000000000000000000
150 38
00000000000000000000000000000000000000
00000000000000000000000000000000000000
...(75 lines omitted)...
0000000003fffffffffffffffff00000000000
0000000003fffffffffffffffff00000000000
...(69 lines omitted)...
00000000000000000000000000000000000000
00000000000000000000000000000000000000
0 0

Sample Output

Case 1: AKW

Case 2: AAAAA

 

题目类型：简单DFS搜索

算法分析：先构造出图片的二进制01矩阵，然后'1'的四连通块的个数就是输出字母的个数，可以给每个'1'连通块打上标记，然后给每个'0'连通块也打上标记，由于发现字母内部所含有的白色“洞”的个数不同，可以依此来分辨字母。只需要依次判断每个'1'相邻的四个位置是否是'0'，并记录相邻的不同标号'0'的数量即可

 

uva572

maksyuki 发表于 oj 分类，标签:
31 5月 2018
0

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil.

A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

Input

The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 ≤ m ≤ 100 and 1 ≤ n ≤ 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either ‘*’, representing the absence of oil, or ‘@’, representing an oil pocket.

Output

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

Sample Input

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

Sample Output

0

1

2

2

 

题目类型：简单DFS搜索

算法分析：直接标记每个相连的石油块即可

 

uva297

maksyuki 发表于 oj 分类，标签:
30 5月 2018
0

A quadtree is a representation format used to encode images. The fundamental idea behind the quadtree is that any image can be split into four quadrants. Each quadrant may again be split in four sub quadrants, etc. In the quadtree, the image is represented by a parent node, while the four quadrants are represented by four child nodes, in a predetermined order.

Of course, if the whole image is a single color, it can be represented by a quadtree consisting of a single node. In general, a quadrant needs only to be subdivided if it consists of pixels of different colors. As a result, the quadtree need not be of uniform depth.

A modern computer artist works with black-and-white images of 32 × 32 units, for a total of 1024 pixels per image. One of the operations he performs is adding two images together, to form a new image. In the resulting image a pixel is black if it was black in at least one of the component images, otherwise it is white.

This particular artist believes in what he calls the preferred fullness: for an image to be interesting (i.e. to sell for big bucks) the most important property is the number of filled (black) pixels in the image. So, before adding two images together, he would like to know how many pixels will be black in the resulting image. Your job is to write a program that, given the quadtree representation of two images, calculates the number of pixels that are black in the image, which is the result of adding the two images together.

In the figure, the first example is shown (from top to bottom) as image, quadtree, pre-order string (defined below) and number of pixels. The quadrant numbering is shown at the top of the figure.

Input

The first line of input specifies the number of test cases (N) your program has to process.

The input for each test case is two strings, each string on its own line. The string is the pre-order representation of a quadtree, in which the letter ‘p’ indicates a parent node, the letter ‘f’ (full) a black quadrant and the letter ‘e’ (empty) a white quadrant. It is guaranteed that each string represents a valid quadtree, while the depth of the tree is not more than 5 (because each pixel has only one color).

Output

For each test case, print on one line the text ‘There are X black pixels.’, where X is the number of black pixels in the resulting image.

Sample Input

3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe

Sample Output

There are 640 black pixels.

There are 512 black pixels.

There are 384 black pixels.

 

题目类型：二叉树递归遍历

算法分析：按照先序遍历的顺序构建，当遇到叶子节点'f'时，直接将其所包含的像素中仍没有计算过的累加起来

 

uva699

maksyuki 发表于 oj 分类，标签:
30 5月 2018
0

Each year, fall in the North Central region is accompanied by the brilliant colors of the leaves on the trees, followed quickly by the falling leaves accumulating under the trees. If the same thing happened to binary trees, how large would the piles of leaves become?

We assume each node in a binary tree ”drops” a number of leaves equal to the integer value stored in that node. We also assume that these leaves drop vertically to the ground (thankfully, there’s no wind to blow them around). Finally, we assume that the nodes are positioned horizontally in such a manner that the left and right children of a node are exactly one unit to the left and one unit to the right, respectively, of their parent. Consider the following tree on the right:

The nodes containing 5 and 6 have the same horizontal position (with different vertical positions, of course). The node containing 7 is one unit to the left of those containing 5 and 6, and the node containing 3 is one unit to their right. When the ”leaves” drop from these nodes, three piles are created: the leftmost one contains 7 leaves (from the leftmost node), the next contains 11 (from the nodes containing 5 and 6), and the rightmost pile contains 3. (While it is true that only leaf nodes in a tree would logically have leaves, we ignore that in this problem.)

Input

The input contains multiple test cases, each describing a single tree. A tree is specified by giving the value in the root node, followed by the description of the left subtree, and then the description of the right subtree. If a subtree is empty, the value ‘-1’ is supplied. Thus the tree shown above is specified as ‘5 7 -1 6 -1 -1 3 -1 -1’. Each actual tree node contains a positive, non-zero value. The last test case is followed by a single ‘-1’ (which would otherwise represent an empty tree).

Output

For each test case, display the case number (they are numbered sequentially, starting with 1) on a line by itself. On the next line display the number of “leaves” in each pile, from left to right, with a single space separating each value. This display must start in column 1, and will not exceed the width of an 80-character line. Follow the output for each case by a blank line. This format is illustrated in the examples below.

Sample Input

5 7 -1 6 -1 -1 3 -1 -1
8 2 9 -1 -1 6 5 -1 -1 12 -1
-1 3 7 -1 -1 -1
-1

Sample Output

Case 1:

7 11 3

 

Case 2:

9 7 21 15

 

题目类型：二叉树递归遍历

算法分析：按照先序遍历建树并更新结果，注意这里对输入的处理

 

uva839

maksyuki 发表于 oj 分类，标签:
30 5月 2018
0

Before being an ubiquous communications gadget, a mobile was just a structure made of strings and wires suspending colourfull things. This kind of mobile is usually found hanging over cradles of small babies.

The figure illustrates a simple mobile. It is just a wire, suspended by a string, with an object on each side. It can also be seen as a kind of lever with the fulcrum on the point where the string ties the wire. From the lever principle we know that to balance a simple mobile the product of the weight of the objects by their distance to the fulcrum must be equal. That is Wl × Dl = Wr × Dr where Dl is the left distance, Dr is the right distance, Wl is the left weight and Wr is the right weight.

In a more complex mobile the object may be replaced by a sub-mobile, as shown in the next figure. In this case it is not so straightforward to check if the mobile is balanced so we need you to write a program that, given a description of a mobile as input, checks whether the mobile is in equilibrium or not.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input is composed of several lines, each containing 4 integers separated by a single space. The 4 integers represent the distances of each object to the fulcrum and their weights, in the format: Wl Dl Wr Dr

If Wl or Wr is zero then there is a sub-mobile hanging from that end and the following lines define the the sub-mobile. In this case we compute the weight of the sub-mobile as the sum of weights of all its objects, disregarding the weight of the wires and strings. If both Wl and Wr are zero then the following lines define two sub-mobiles: first the left then the right one.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. Write ‘YES’ if the mobile is in equilibrium, write ‘NO’ otherwise.

Sample Input

1
0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2

Sample Output

YES

 

题目类型：二叉树递归遍历

算法分析：按照后序遍历判断是否满足条件，注意这里对输入的处理

 

uva548

maksyuki 发表于 oj 分类，标签:
30 5月 2018
0

You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path.

Input

The input file will contain a description of the binary tree given as the inorder and postorder traversal sequences of that tree. Your program will read two line (until end of file) from the input file. The first line will contain the sequence of values associated with an inorder traversal of the tree and the second line will contain the sequence of values associated with a postorder traversal of the tree. All values will be different, greater than zero and less than 10000. You may assume that no binary tree will have more than 10000 nodes or less than 1 node.

Output

For each tree description you should output the value of the leaf node of a path of least value. In the case of multiple paths of least value you should pick the one with the least value on the terminal node.

Sample Input

3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255

Sample Output

1

3

255

 

题目类型：二叉树递归遍历

算法分析：按照题目要求使用二叉树的中序遍历和后序遍历来建树，然后使用DFS计算出题目中的最小叶子。注意递归建树时的边界条件和每次DFS递归中的实参的值