A typical Q1-level problem is to draw some ASCII triangles. Well, after a bunch of students wrote their attempts, it’s time to count the mess. Given a grid with some pattern, how many different triangles could it have been? The ASCII triangles have shapes such as:
# # ### # ### ##### etc
The input file DATA3.txt will contain 5 test cases. The first line of each case is a number 1 ≤ N ≤ 256 representing the size of the square grid, followed by N lines describing the grid.
The output file OUT3.txt will contain 5 lines of output. Each is a count of the number of different triangles that exist in the grid. The orientation of the triangles is just as shown above, for the sake of simplicity. In the sample case below, there are 11 triangles of size one, 4 of size three, and 1 of size five, for a total of 11 + 4 + 1 = 16. (The ASCII pattern doesn’t support triangles of even length.)
5
.....
.###.
.###.
#####
.....
16