사각형 개수 세기

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

요약
1부터 9까지의 값이 적힌 N 곱하기 M 격자에서 네 꼭짓점 값의 합이 20이 되는 축에 평행한 사각형의 개수를 센다.
난이도

보통10점 중 7점

유형
조합론, 수학, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

N×MN \times M 격자의 (i,j)(i, j) 칸에는 11 이상 99 이하의 숫자 A_i,jA\_{i, j}가 쓰여있다. 다음을 만족하는 (x_1,x_2,y_1,y_2)(x\_1, x\_2, y\_1, y\_2) 순서쌍의 개수를 세자.

  • 1≤x_1<x_2≤N1 \leq x\_1 < x\_2 \leq N, 1≤y_1<y_2≤M1 \leq y\_1 < y\_2 \leq M
  • A_x_1,y_1+A_x_1,y_2+A_x_2,y_1+A_x_2,y_2=20A\_{x\_1, y\_1} + A\_{x\_1, y\_2} + A\_{x\_2, y\_1} + A\_{x\_2, y\_2} = 20

입력

첫 줄에는 NN과 MM이 공백으로 구분되어 주어진다.

이후 NN개의 줄에 걸쳐 A_i,1,A_i,2,⋯ ,A_i,MA\_{i, 1}, A\_{i, 2}, \cdots, A\_{i, M}이 공백으로 구분되어 주어진다.

출력

위 조건을 만족하는 (x_1,x_2,y_1,y_2)(x\_1, x\_2, y\_1, y\_2)의 개수를 출력하라.

제한

  • 2≤N,M≤1052 \leq N, M \leq 10^5
  • NM≤105NM \leq 10^5
  • 1≤A_i,j≤91 \leq A\_{i, j} \leq 9

예제1

  1. 예제 1

    입력
    4 5
9 9 3 2 7
5 4 4 1 2
7 1 7 6 7
7 4 7 3 2
    예상 출력
    4