链接: https://cses.fi/problemset/task/2137

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个 $n \times n$ 的网格，其中每个方格要么是黑色，要么是白色。如果一个子网格的高度和宽度都至少为 2，且它的四个角都是黑色，则称其为「美丽的」。在给定的网格中，有多少个美丽的子网格？

输入

第一行有一个整数 $n$：网格的大小。

之后有 $n$ 行描述网格：1 表示该方格为黑色，0 表示该方格为白色。

输出

输出美丽的子网格的数量。

数据范围

$1 \le n \le 3000$

样例输入

5
00010
11111
00110
11001
00010

样例输出

4