2014 Canadian Computing Competition, Stage 2

Day 1, Problem 1: Troyangles

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, …, h. The rows are centred above each other so that they are symmetrically about a vertical line down their middle.

Input

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

You can assume that for test cases worth 20% of the marks, N ≤ 50.

Output

Output the number of triangles in the grid.

Sample Input

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

Sample Output

16

Explanation

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

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: May 17, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)