CCO '14 P1 - Troyangles

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types
Canadian Computing Competition: 2014 Stage 2, Day 1, Problem 1

Troy loves triangles. He especially likes counting triangles. He has an -by- grid consisting of either . or # characters. Help him count the number of triangles formed only by # characters in the grid. Triangles are of the form

          #
#    ###
#, ###, #####, etc.

More formally, a triangle of height consists of rows for some positive integer . The -th row contains # characters for . The rows are centred above each other so that they are symmetrical about a vertical line down their middle.

Input Specification

The first line contains the number () representing the size of the grid. The next lines each contain characters as described above.

You can assume that for testcases worth 20% of the marks, .

Output Specification

Output the number of triangles in the grid.

Sample Input

5
.....
.###.
.###.
#####
.....

Output for Sample Input

16

Explanation of Output for Sample Input

There are triangles of height one, triangles of height two, and triangle of height three.