题目描述

给定一个 $N \times N$ 的字符矩阵，其中只包含 0 和 1。请选择两个不同的行和两个不同的列，它们的四个交点组成一个边与矩阵边界平行的矩形。

求四个角上的字符均为 1 的矩形数量。

输入格式

第一行包含一个整数 $N$。

接下来 $N$ 行，每行包含一个长度为 $N$ 的 01 字符串。

输出格式

输出一个整数，表示满足条件的矩形数量。

3
011
101
111

2

4
1101
1011
1111
1111

19

数据范围与提示

• 对于 $50\%$ 的数据，$1 \le N \le 100$
• 对于全部数据，$1 \le N \le 300$