CCO '14 P1 - Troyangles

View as PDF

Submit solution

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

Problem types

Troy loves triangles. He especially likes counting triangles. He has an N-by-N 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 h consists of h rows for some positive integer h. The i-th row contains 2i - 1 # characters for i = 1, \ldots, h. 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 N (1 \le N \le 2000) representing the size of the grid. The next N lines each contain N characters as described above.

You can assume that for testcases worth 20% of the marks, N \le 50.

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 11 triangles of height one, 4 triangles of height two, and 1 triangle of height three.


Comments