题目描述

给定一个 $n\times m$ 的只包含 $0$ 和 $1$ 的矩阵，以及一个正整数 $k$。请统计矩阵中一共有多少个 $k\times k$ 的子正方形，其内部所有元素都是 $1$。

本题数据范围弱化为 $n,m\leq 20$，可直接用枚举所有 $k\times k$ 窗口的暴力方法求解（无需前缀和/动态规划）。

输入格式

输入文件第一行为三个整数 $n,m,k$（$1\leq n,m\leq 20$，$1\leq k\leq\min(n,m)$），接下来 $n$ 行，每行 $m$ 个数字，用空格隔开，$0$ 或 $1$。

输出格式

一个整数，满足条件的 $k\times k$ 全 $1$ 正方形个数。

4 4 2
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

2

提示

$(1\leq n,m\leq 20,\;1\leq k\leq\min(n,m))$