respectively. There will be one machine gun shooting through each opening.
Here we assume that a bullet is so powerful that it can run across any
distance and destroy a blockhouse on its way. On the other hand, a wall is
so strongly built that can stop the bullets.

11

The goal is to place as many blockhouses in a city as possible so that no
two can destroy each other. A configuration of blockhouses is legal
provided that no two blockhouses are on the same horizontal row or vertical
column in a map unless there is at least one wall separating them. In this
problem we will consider small square cities (at most 4x4) that contain
walls through which bullets cannot run through.

The following image shows five pictures of the same board. The first
picture is the empty board, the second and third pictures show legal
configurations, and the fourth and fifth pictures show illegal
configurations. For this board, the maximum number of blockhouses in a
legal configuration is 5; the second picture shows one way to do it, but
there are several other ways.

□■□□
●■□●
□■●□
□■□□
□■□□
□□□□
□●□□
□●□□
●□□●
□□●□
■■□□
■■●□
■■●□
■■□□
■■□□
□□□□
●□□□
●□□□
□□□□
□□●□


Your task is to write a program that, given a description of a map,
calculates the maximum number of blockhouses that can be placed in the city
in a legal configuration.


The input file contains one or more map descriptions, followed by a line
containing the number 0 that signals the end of the file. Each map
description begins with a line containing a positive integer n that is the
size of the city; n will be at most 4. The next n lines each describe one
row of the map, with a '.' indicating an open space and an uppercase 'X'
indicating a wall. There are no spaces in the input file.



For each test case, output one line containing the maximum number of
blockhouses that can be placed in the city in a legal configuration.

Sample input:

4
.X..
....
XX..
....

2
XX
.X

3
.X.

X.X
.X.

3
...
.XX
.XX

4
....
....
....


....

0

Sample output:

5
1
5
2
4

Trees are fundamental in many branches of computer science. Current state-of-t
he art parallel computers such as Thinking Machines' CM-5 are based on fat tre
es. Quad- and octal-trees are fundamental to many algorithms in computer graph
ics.

This problem involves building and traversing binary trees.

Given a sequence of binary trees, you are to write a program that prints a lev
el-order traversal of each tree. In this problem each node of a binary tree co
ntains a positive integer and all binary trees have fewer than 256 nodes.

In a level-order traversal of a tree, the data in all nodes at a given level a
re printed in left-to-right order and all nodes at level k are printed before
all nodes at level k+1.

For example, a level order traversal of the tree


is: 5, 4, 8, 11, 13, 4, 7, 2, 1.
参考试题2:
In this problem a binary tree is specified by a sequence of pairs (n,s) where
n is the value at the node whose path from the root is given by the string s.
A path is given be a sequence of L's and R's where L indicates a left branch a
nd R indicates a right branch. In the tree diagrammed above, the node containi
ng 13 is specified by (13,RL), and the node containing 2 is specified by (2,LL
R). The root node is specified by (5,) where the empty string indicates the pa
th from the root to itself. A binary tree is considered to be completely speci
fied if every node on all root-to-node paths in the tree is given a value exac
tly once.
Input
The input is a sequence of binary trees specified as described above. Each tre
e in a sequence consists of several pairs (n,s) as described above separated b
y whitespace. The last entry in each tree is (). No whitespace appears between
left and right parentheses.
All nodes contain a positive integer. Every tree in the input will consist of
at least one node and no more than 256 nodes. Input is terminated by end-of-fi