This page is still under construction.

Parts of this page are still being built. What you see may change.

Triangles

Time limit1sMemory limit128 MB

Summary
In each triangular grid of white and black cells, find the area of the largest all-white triangle, which may point up or down.
Level

Medium6 of 10

Topics
Dynamic programming, Array, Implementation, Brute force
Solved
No attempts yet

Problem

It is always great to have little brothers or sisters. You can tease them, lock them in the bathroom, or put red-hot chili in their sandwiches. But sooner or later, all that mischief comes back to you!

In one month it will be Christmas, and this year you have the honor of making the big star that goes on top of the Christmas tree. But when you receive the triangle-patterned silver paper, you notice that it is full of holes: your little sister has already cut out smaller triangles for ordinary Christmas stars. Your only hope is to find an algorithm that, for each piece of silver paper, tells you the size of the largest triangle that is still intact.

Given a triangular structure made of white and black fields, find the area (number of fields) of the largest triangle that consists only of white fields.

Input

The input contains several triangle descriptions. The first line of each description contains an integer nn (1≤n≤1001 \le n \le 100), the height of the triangle. The next nn lines contain the rows of the triangle using the characters space, #, and -, where # is a black field and - is a white field. Spaces are used only to keep the triangle shape by padding the left end of each line.

For each triangle, the number of # and - characters per line is odd and decreases from 2n−12n-1 on the first line down to 1 on the last line.

The input is terminated by a description whose height nn is 0.

Output

For each triangle, first print its number in the form Triangle #k (the first triangle is number 1). Then print the line The largest triangle area is a., where aa is the number of fields inside the largest triangle that consists only of white fields. Note that the largest triangle may point upward, as in the second example. Print a blank line between the outputs of consecutive triangles.

Examples3

  1. Example 1

    Input
    5
    #-##----#
     -----#-
      ---#-
       -#-
        -
    4
    #-#-#--
     #---#
      ##-
       -
    0
    
    Expected output
    Triangle #1
    The largest triangle area is 9.
    
    Triangle #2
    The largest triangle area is 4.
    
  2. Example 2

    Input
    5
    ---------
     -------
      -----
       ---
        -
    0
    
    Expected output
    Triangle #1
    The largest triangle area is 25.
    
  3. Example 3

    Input
    2
    ---
     -
    2
    ###
     #
    3
    -----
     ---
      -
    0
    
    Expected output
    Triangle #1
    The largest triangle area is 4.
    
    Triangle #2
    The largest triangle area is 0.
    
    Triangle #3
    The largest triangle area is 9.