#P18285. Trash Problem

Trash Problem

Trash Problem

给定一个 n×nn\times n 的网格,每个格子要么是黑色(0),要么是白色(1)。

请计算有多少个矩形区域满足以下条件:区域内所有白色格子可以恰好被若干个互不重叠的 2×22\times2 正方形覆盖,且没有任何黑色格子被覆盖。每个正方形都必须完全位于该矩形区域内,并由四个白色格子组成。

输入格式

第一行包含一个正整数 nn,满足 1≤n≤3001\le n\le300。

接下来 nn 行,每行包含一个长度为 nn、仅由字符 0 和 1 组成的字符串,依次表示网格各行。

输出格式

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

样例

4
0110
0110
1111
1111
17

备注

不包含任何白色格子的矩形也满足条件,必须计入答案。