Piramid

piramid

== include(page="template/taskheader" task_id="piramid") ==

Zoe are o matrice patratica cu $N$ linii si $N$ coloane plina cu $0$ sau $1$. Ea vrea sa numere cate piramide avand pe *margine* doar elemente egale cu $1$ exista in matrice. O piramida este un triunghi dreptunghic isoscel cu ipotenuza paralela cu doua dintre marginile matricei.

Zoe are o matrice patratica cu $N$ linii si $N$ coloane plina cu $0$ sau $1$. Ea ar dori sa numere cate piramide **goale** formate doar din elemente egale cu $1$ exista in matrice. Bineinteles ca va roaga pe voi sa o ajutati.

Mai jos se afla cateva exemple de piramide de diverse laturi. Observati ca o piramida se poate roti de oricate ori cu 90 de grade.
table(example). |_. Latura 1 |_. Latura 2 |_. Latura 3 |_. Latura 4 |_. Latura 2 |_. Latura 3 |_. Latura 1 |

table(example). |_. Ordin 1 |_. Ordin 2 |_. Ordin 3 |_. Ordin 4 |_. Ordin 2 rotit |_. Ordin 3 rotit |_. Ordin 1 rotit |

| 0 0 0 0 0
0 0 **1** 0 0
0 **1 1 1** 0

h2. Date de intrare

Fişierul de intrare $piramid.in$ va contine pe prima linie numarul natural $N$ reprezentand dimensiunea matricei. Urmatoarele $N$ linii vor contine fiecare cate $N$ caractere $0$ sau $1$, **nedespartite prin spatii**.

Fişierul de intrare $piramid.in$ ...

h2. Date de ieşire

În fişierul de ieşire $piramid.out$ veti afisa un singur numar $M$, reprezentand numarul total de piramide ce respecta conditiile din enunt care se afla in matricea din fisierul de intrare.

În fişierul de ieşire $piramid.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 1000$
* Se garanteaza ca rezultatul nu va depasi $10^9^$
* Piramida minima este cea de latura 1 din exemplul de mai sus

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. piramid.in |_. piramid.out |

| 10
0000001000
0000101100
0001011010
0010001100
0111111100
0000100000
0001111100
0010101000
0110010000
0010000000
|15 |
|7
1111111
1111111
1111111
1111111
1111111
1111111
1111111
|196|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicaţie

Primul exemplu: Sunt $3$ piramide de latura mai mare ca $1$, si inca $12$ (mai greu de observat) de latura $1$.
Al doilea exemplu: *Atentie!* Se vor numara piramidele indiferent de ceea ce contin in interior. Singura restrctie impusa este ca marginile sa fie formate doar din elemente de $1$.

...

== include(page="template/taskfooter" task_id="piramid") ==

4538