코드자몬 트레이너는 몬스터를 열심히 찾고 있지만, 숙련자가 아니면 몬스터는 정말 위험할 수 있다. 몬스터가 없는 안전한 장소를 찾는 것도 좋다.
우리의 세계를 격자라고 간주했다 했을 때, 일부 칸은 몬스터가 점령했다. 우리는 몬스터가 전혀 없는 안전한 정사각형 형태의 격자를 D x D 사각형(D>=1)으로 정의한다. 여러분은 우리의 세계의 몇 개의 안전한 정사각형(가능한 모든 크기)이 몇 개 있는지 알아내야한다.
입력
첫 번째 줄은 테스트 케이스 수 T를 정수로 입력받는다.
각 테스트 케이스의 첫 줄은 세계를 그리드로 표현한 격자에 대해 행의 개수 R, 열의 개수 C, 몬스터의 개수 K개가 정수로 입력받는다. 이 다음은 K개의 줄만큼 입력받으며, 몬스터가 위치하는 칸의 좌표의 행인 Ri과 열 Ci가 주어진다. 행은 위에서부터 아래로 번호가 매겨지며, 열은 왼쪽에서 오른쪽으로 번호가 매겨진다. 행과 열은 0부터 시작된다.
출력
각 테스트 케이스에 대해 Case #x: y를 포함하는 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호고, y는 테스트 케이스의 총 안전 구역의 갯수다.
wlskrla7 1년 전
코드자몬 트레이너는 몬스터를 열심히 찾고 있지만, 숙련자가 아니면 몬스터는 정말 위험할 수 있다. 몬스터가 없는 안전한 장소를 찾는 것도 좋다.
우리의 세계를 격자라고 간주했다 했을 때, 일부 칸은 몬스터가 점령했다. 우리는 몬스터가 전혀 없는 안전한 정사각형 형태의 격자를 D x D 사각형(D>=1)으로 정의한다. 여러분은 우리의 세계의 몇 개의 안전한 정사각형(가능한 모든 크기)이 몇 개 있는지 알아내야한다.
입력
첫 번째 줄은 테스트 케이스 수 T를 정수로 입력받는다.
각 테스트 케이스의 첫 줄은 세계를 그리드로 표현한 격자에 대해 행의 개수 R, 열의 개수 C, 몬스터의 개수 K개가 정수로 입력받는다. 이 다음은 K개의 줄만큼 입력받으며, 몬스터가 위치하는 칸의 좌표의 행인 Ri과 열 Ci가 주어진다. 행은 위에서부터 아래로 번호가 매겨지며, 열은 왼쪽에서 오른쪽으로 번호가 매겨진다. 행과 열은 0부터 시작된다.
출력
각 테스트 케이스에 대해 Case #x: y를 포함하는 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호고, y는 테스트 케이스의 총 안전 구역의 갯수다.