cho.sh

안전한 정사각형 (작은 입력)

R행 C열 격자에서 몬스터가 없는 D x D 정사각형 부분격자의 개수를 모두 센다.

보통4동적 계획법행렬누적 합구현면접 대비아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

코드자몬 트레이너는 몬스터를 찾아 돌아다니지만, 트레이너가 아닌 사람에게 몬스터는 아주 위험하다. 몬스터가 한 마리도 없는 안전한 자리를 찾아야 한다.

세상을 격자로 보자. 일부 칸에는 몬스터가 있다. 안전한 정사각형은 격자에 맞춰 놓인 D×DD \times D 크기의 칸 묶음 중 몬스터가 하나도 없는 것이다. 여기서 D≥1D \ge 1이다. 세상 전체에 안전한 정사각형이 크기에 관계없이 몇 개 있는지 구하라.

입력

첫 줄에 테스트 케이스의 개수 TT가 주어진다. 이어서 TT개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 RR, CC, KK가 주어진다. 격자는 RR개의 행과 CC개의 열로 이루어지고, 그 안에 몬스터가 KK마리 있다. 이어서 KK개의 줄이 주어진다. 각 줄에는 ii번째 몬스터가 있는 칸의 행 번호 RiR_i와 열 번호 CiC_i가 주어진다. 행 번호는 위에서 아래로 0부터 매기고, 열 번호는 왼쪽에서 오른쪽으로 0부터 매긴다.

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, yy는 그 테스트 케이스의 안전한 정사각형 개수이다.

제한

  • 1≤T≤201 \le T \le 20
  • 1≤R≤1001 \le R \le 100
  • 1≤C≤1001 \le C \le 100
  • 0≤K≤min⁡(R×C,100)0 \le K \le \min(R \times C, 100)
  • 0≤Ri<R0 \le R_i < R
  • 0≤Ci<C0 \le C_i < C
  • i≠ji \ne j이면 (Ri,Ci)≠(Rj,Cj)(R_i, C_i) \ne (R_j, C_j)이다. 한 칸에 몬스터가 두 마리 이상 있는 경우는 없다.

힌트

예제의 첫 번째 테스트 케이스의 격자는 다음과 같다.

0 0 0
0 0 0
0 1 0

0은 몬스터가 없는 칸, 1은 몬스터가 있는 칸이다. 안전한 정사각형은 10개이며, 1×11 \times 1이 8개, 2×22 \times 2가 2개이다.

두 번째 테스트 케이스의 격자는 다음과 같다.

0 1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1 0
1 0 0 0 1 0 0 0 0 1 1
0 0 0 0 1 0 0 0 0 0 1

안전한 정사각형은 51개이며, 1×11 \times 1이 32개, 2×22 \times 2가 13개, 3×33 \times 3이 5개, 4×44 \times 4가 1개이다.