십자 찾기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

N×M 이진 격자에서 중심 칸의 위, 아래, 왼쪽, 오른쪽으로 K칸 안의 칸이 모두 1인 크기 K짜리 십자가의 개수를 구합니다.

문제

쿠는 $N\times M$ 크기의 모눈종이를 임의로 색칠한다. 색칠하던 도중 쿠는 모눈종이에서 특정 크기의 십자 모양이 몇 개나 있는지 궁금해졌다.

$(r, c)$ 위치의 모눈을 기준으로 $(r-K, c)$ 부터 $(r+K, c)$ 까지, 그리고 $(r, c-K)$ 부터 $(r, c+K)$ 까지 연속해서 색칠되어 있으면 $(r, c)$ 에 크기가 $K$ 인 십자가 있다고 정의한다.

크기가 각각 $0$ , $1$ , $2$ 인 십자는 아래 그림과 같다. 크기가 $K$ 인 십자의 개수를 구하라.

첫째 줄에 모눈종이의 크기 $N$ 과 $M$ 이 공백으로 구분되어 주어진다. $\left(1\leq N, M\leq 2,500\right)$

둘째 줄에 십자의 크기 $K$ 가 주어진다. $\left(0\leq K\leq \left\lfloor\frac{min(N-1,\,M-1)}{2}\right\rfloor\right)$

셋째 줄부터 $N$ 줄에 걸쳐 모눈의 색칠 여부가 공백으로 구분되어 주어진다. 해당 위치가 색칠되어 있으면 1, 아니면 0이다.

크기가 $K$ 인 십자의 개수를 출력한다.

예제 1

입력

5 6
1
0 1 0 1 1 0
1 1 1 1 1 1
0 1 1 1 1 0
0 0 1 0 1 0
1 0 1 1 1 1

예상 출력