Friday Evening Python Homework 07.05.

07 Jul Friday Evening Python Homework 07.05.

Question:

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

More formally, a triangle of height h consists of h rows for some positive integer h. The ith row contains 2i − 1 “#” characters for i = 1, . . . , 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 ≤ N ≤ 2000) representing the size of the grid. The next N lines each contain N characters as described above.

Output Specification
Output the number of triangles in the grid.

Sample Input

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.