숲속 산불

면접 대비

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

요약

무한한 격자에서 불이 상하좌우로 번지고 잘린 나무가 이를 막을 때, T분 뒤에도 타고 있는 나무의 수를 구합니다.

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

문제

숲속에 큰 산불이 났다! 이 숲은 정수 좌표마다 나무가 한 그루씩 있는 끝없이 넓은 2차원 평면이다. 지금 $N$ 그루의 나무가 불에 타고 있다. 1분마다 불은 타고 있는 나무에서 북, 동, 서, 남쪽의 네 이웃 나무로 옮겨 붙는다. 산불을 막으려고 소방대가 $M$ 그루의 나무를 베어 냈다. 베어진 나무는 불이 붙지 않으므로 이 지점들은 벽 역할을 한다. 이 불이 얼마나 큰 피해를 낼지 알고 싶다. $T$ 분 뒤에는 큰 비가 내려 불을 모두 끈다. 따라서 $T$ 분이 지났을 때 불에 타고 있는 나무가 몇 그루인지 구하라.

입력

첫째 줄에 정수 세 개 $N$ , $M$ , $T$ 가 주어진다. $N$ 은 불에 타고 있는 나무의 수( $1 \leq N \leq 100$ ), $M$ 은 베어진 나무의 수( $0 \leq M \leq 100$ ), $T$ 는 큰 비가 내리기까지의 시간(분, $0 \leq T \leq 10^9$ )이다. 다음 $N$ 개 줄에는 불에 타고 있는 나무의 좌표 $x_i, y_i$ ( $0 \leq x_i, y_i < 10^5$ )가, 그다음 $M$ 개 줄에는 베어진 나무의 좌표 $x_i, y_i$ ( $0 \leq x_i, y_i < 10^5$ )가 주어진다. 어떤 두 나무도 같은 좌표에 놓이지 않는다. 불에 타고 있든 베어졌든 마찬가지다.

출력

$T$ 분 뒤에 불타고 있는 나무의 수를 정수 하나로 출력한다.

힌트

예제 1에서 불은 $(0,2)$ , $(1,3)$ , $(2,2)$ 로 번진다. 따라서 불타고 있는 나무는 모두 4그루다. 예제 2에서 불타고 있는 나무는 베어진 나무에 둘러싸여 있다. 따라서 $T$ 가 아무리 커도 불타는 나무는 한 그루뿐이다. 예제 3에서는 $T = 0$ 이라 불이 번지지 않으므로 답은 4다.

예제4

예제 1
입력
```
1 1 1
1 2
1 1
```
예상 출력
```
4
```
예제 2
입력
```
1 4 12345678
2 2
1 2
2 1
2 3
3 2
```
예상 출력
```
1
```
예제 3
입력
```
4 1 0
1 1
1 2
2 3
3 4
7 7
```
예상 출력
```
4
```
예제 4
입력
```
1 2 100000
0 0
2 1
1 2
```
예상 출력
```
20000199999
```