#P18285. Trash Problem
Trash Problem
Trash Problem
给定一个 的网格,每个格子要么是黑色(0),要么是白色(1)。
请计算有多少个矩形区域满足以下条件:区域内所有白色格子可以恰好被若干个互不重叠的 正方形覆盖,且没有任何黑色格子被覆盖。每个正方形都必须完全位于该矩形区域内,并由四个白色格子组成。
输入格式
第一行包含一个正整数 ,满足 。
接下来 行,每行包含一个长度为 、仅由字符 0 和 1 组成的字符串,依次表示网格各行。
输出格式
输出一个整数,表示满足条件的矩形区域数量。
样例
4
0110
0110
1111
1111
17
备注
不包含任何白色格子的矩形也满足条件,必须计入答案。