The Archaeologist's Trouble II
Time Limit: 1 Second Memory Limit: 32768 KB
Lazy Genius, a Archaelogist, recently found a lot of ancient steles, on which
there are only two kinds of characters, '*'and '@'. The characters formed a
equilateral triangle on each steles. The triangle has N lines.The ith line contain
i characters.
e.g. a triangle with 4 lines:
* * @ * @ * @ * @ *
Through hard researchs, he found some rules of arrange of characters. There are only 4 styles of arranges of any three adjacent characters:
* @ @ * * @, @ *, * @, @ *
Through hundreds of thousands of years, most of steles have become hard to identify. With the rules above, Mr.Genius recovered many steles. However, there are too many steles to be recovered by hand. Now Mr.Genius turns to you, a gifted programming student. He believes that you could help him.
Your task is to find out the maximum number and the minimum number of '@' of a given stele.
Input
The input contains several test cases.
The first line of each test block is a positive integer, N (1 < N <= 100),
which represents the size of the triangle.
After that follows N lines. the ith lines contains i characters. The charatcter
could only be '@', '*' or '?', where '?' represents the unclear characters.
The input is terminated by a negative integer.
Output
output a line contain two integers for each test block, the maximum and the minimum.
Sample Input
2 * ?? 3 ? ?? ??? 5 ? *@ ?*? ???? ????? -1
Sample Output
1 1 4 2 9 7Submit
Source: ZOJ Monthly, December 2003