### 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 2`i` − 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)

It's quiet in here...