Problem Description

Given an $n \times n$ $01$ square matrix, compute the number of X’s in it.

An X is defined as a connected component filled with $1$’s and shaped like an X. Specifically, an X is made up of a left-leaning diagonal \ and a right-leaning diagonal /. You must ensure that the left-leaning diagonal and the right-leaning diagonal have the same length, and the X is centrally symmetric. The diagonal length must be greater than $1$.

For example:

101
010
101

There is one X with diagonal length $3$.

1001
0110
0110
1001

There are two X’s with diagonal lengths $2$ and $4$.

10001
01010
00100
01010
00001

There is only one X with diagonal length $3$.

Input Format

Line $1$ contains one positive integer $n$.

The next $n$ lines each contain a $01$ string of length $n$, describing a $01$ matrix.

Output Format

Output one line containing a non-negative integer, representing the number of X’s.

5
10001
01010
00100
01011
00011

2

Hint

For $20\%$ of the testdata, $1 \leq n \leq 3$.

For $40\%$ of the testdata, $1 \leq n \leq 10$.

For $70\%$ of the testdata, $1 \leq n \leq 50$.

For $100\%$ of the testdata, $1 \leq n \leq 100$.

Translated by ChatGPT 5