폭발의 연쇄

면접 대비

시간 제한8초메모리 제한512 MB

요약

한 폭탄이 터지면 같은 행과 열로 D칸 안의 폭탄이 연쇄적으로 폭발할 때, 처음 지정한 폭탄을 터뜨렸을 때 최종적으로 폭발하는 폭탄 수를 센다.

난이도: 보통10점 중 4점
유형: 그래프, BFS, 시뮬레이션, 구현
정답자: 아직 제출이 없습니다

문제

당신은 폭탄을 사용하는 게임을 하고 있다. 이 게임의 필드는 너비 W 칸, 높이 H 칸의 격자이다. 필드의 왼쪽에서 x번째 열, 위에서 y번째 행의 칸은 (x, y)로 나타낸다.

이 필드 위에 N개의 폭탄이 배치되어 있고, i번째 폭탄의 위치는 (xi, yi)이다. 이 게임의 폭탄은 폭발할 때 폭탄이 있는 칸에서 상하좌우 각 방향으로 D칸 이내의 십자 모양 영역 안에 있는 폭탄을 유폭시켜 사라지게 한다. 또, 폭탄은 다른 폭탄에 의해 유폭될 때도 연쇄하여 폭발한다. 이 폭발은 더 이상 폭발할 폭탄이 없을 때까지 계속된다.

이 게임을 공략하려면 어떤 폭탄을 폭발시켰을 때 모두 몇 개의 폭탄이 폭발하는지 아는 것이 중요하다. 당신은 공략을 유리하게 진행하기 위한 프로그램을 만들기로 했다.

예로, 입력 샘플의 마지막 데이터 세트는 아래 그림과 같다. 이 데이터 세트에서는 (4, 1) 위치에 있는 4번째 폭탄이 처음 폭발한다. 그 뒤 폭발은 다음과 같이 연쇄한다.

(4, 1) 위치의 폭탄이 상하좌우 각 방향으로 3칸 이내에 있는 폭탄을 유폭시킨다.
(5, 1)과 (4, 4) 위치의 폭탄이 유폭으로 연쇄 폭발하여, 각각의 상하좌우 각 방향으로 3칸 이내에 있는 폭탄을 유폭시킨다.
(3, 4)와 (1, 4) 위치의 폭탄이 유폭으로 연쇄 폭발한다. 이때 새로 유폭되는 폭탄은 없다.

따라서 (4, 1) 위치의 폭탄이 폭발하면 모두 5개의 폭탄이 폭발한다.

입력

입력은 최대 50개의 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 나타낸다.

W H N D B
x1 y1
x2 y2
...
xN yN

각 데이터 세트는 N+1행으로 이루어진다.

1행은 필드의 너비 W (1 ≤ W ≤ 100), 높이 H (1 ≤ H ≤ 100), 폭탄의 수 N (1 ≤ N ≤ min(100, WH)), 폭탄의 폭발 크기 D (1 ≤ D ≤ 100), 처음 폭발하는 폭탄의 번호 B (1 ≤ B ≤ N)를 나타내는 정수이다.

2행부터 이어지는 N행은 각각 N개의 폭탄 위치를 나타낸다. i + 1행은 i번째 폭탄의 위치 (xi, yi)를 나타내는 정수이고 1 ≤ xi ≤ W, 1 ≤ yi ≤ H를 만족한다. 각 데이터 세트에서 같은 칸에 여러 폭탄이 배치되는 일은 없다.

입력의 끝은 5개의 0으로 이루어진 행으로 나타낸다.

출력

각 데이터 세트에 대해 처음에 B번째 폭탄이 폭발했을 때 최종적으로 폭발하는 폭탄의 수를 1행에 출력한다.

예제1

예제 1

입력

10 5 5 3 1
1 5
2 5
5 5
5 4
10 5
50 50 1 100 1
25 25
1 100 7 10 4
1 5
1 10
1 40
1 50
1 55
1 63
1 74
3 3 5 3 5
1 1
1 3
3 1
3 3
2 2
20 20 10 10 1
5 5
20 5
5 10
20 8
5 20
10 10
17 17
11 10
8 9
11 20
5 5 7 3 4
1 4
2 2
3 4
4 1
4 4
5 1
5 5
0 0 0 0 0

예상 출력