십자 찾기

면접 대비

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

요약
세로와 가로로 길이 K인 팔이 모두 색칠된, 크기 K인 십자의 중심 칸 개수를 센다.
난이도

보통10점 중 5점

유형
누적 합, 배열, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

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

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

크기가 각각 0,1,20, 1, 2인 십자는 아래의 그림과 같을 때, 크기가 KK인 십자의 개수를 구해보자.

입력

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

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

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

출력

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

예제1

  1. 예제 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
    예상 출력
    4