댐

댐

 

문제

---

어느 마을 안에는 큰 호수가 있고, 그것을 막는 댐이 있었다. 그런데 어느날 그 댐이 무너져내려 호수에 있는 물이 마을을 모두 뒤덮으려한다. 호수에 있는 물은 다음 1시간에 한 블럭으로 이동하며, 물의 양은 무한하다 가정하자. 물은 상 하 좌 우로 퍼져나가며 마을을 뒤덮는다.

당신은 댐이 터진 순간 이 마을의 지도를 받았다. 당신이 도와줘야 할 일은 완공시간이 K시간인 댐들을 최대한 빨리 지어서 물이 더 이상 진행하지 못하도록 하는 것이다.

 

입력

---

첫 줄에는 배열의 크기인 T(1 ≤ T ≤100)가 주어지고 다음 줄부터 배열의 값이 주어진다. 0은 텅 빈 길, 1은 건물이다. (물은 건물을 뒤덮지 못한다고 가정한다.) 그리고 그 다음 줄에는 호수의 좌표 x, y가 주어지고, 다음 줄에는 댐이 지어지는 시간인 K가 주어진다.

 

출력

---

지어야 하는 댐의 숫자를 출력한다. 만약, 마을이 전부 잠길 때까지 댐을 지을 수 없거나 건물에 둘러쌓여 물이 더이상 진행을 못할 경우엔 "-1"을 출력한다.

 

예제 입력 1

5
0 1 0 0 1
0 0 0 0 0
1 1 1 0 1
0 0 0 0 0
1 0 1 0 1
1 1
5

예제 출력 1

3

예제 입력 2

5
0 0 1 0 0
0 0 0 0 0
1 1 1 0 0
0 0 1 1 0
0 0 0 0 0
5 2
3

예제 출력 2

2

 

입출력 설명

첫 번째 입력에서 (1,1) 위치에서 물이 터졌다면, 물은 시간마다 다음과 같이 진행된다.
(B는 건물의 위치)

0 B 4 5 B
1 2 3 4 5
B B B 5 B
9 8 7 6 7
B 9 B 7 B

그러므로 5 시간인 세군데를 막아 물이 진행하지 못하게 하는 것이 최선이다.
그러므로 출력이 3