#P18792. [Omi2018] 墨西哥城地图
[Omi2018] 墨西哥城地图
[Omi2018] 墨西哥城地图
题目描述
一张地图被划分为 行、 列的方格,每个格子上有一个字符 0 或 1。1 表示一个可以游览的地点,0 表示普通格子。
你希望从地图中截取一个非空的矩形子地图,使其中恰好包含 个可以游览的地点。
请计算满足条件的矩形子地图有多少个。矩形的四条边均沿方格边界;只要包含的格子集合不同,就视为不同矩形。
输入格式
第一行包含三个整数 。
接下来 行,每行包含一个长度为 的 01 字符串,表示地图。
输出格式
输出一个整数,表示包含恰好 个 1 的非空矩形数量。
答案可能超过 32 位有符号整数的范围。
样例输入
3 3 2
101
000
101
样例输出
8
数据范围
- ;
- 。
其中,20 分的数据满足 ,其余 80 分没有额外限制。