-
댐
문제
어느 마을 안에는 큰 호수가 있고, 그것을 막는 댐이 있었다. 그런데 어느날 그 댐이 무너져내려 호수에 있는 물이 마을을 모두 뒤덮으려한다. 호수에 있는 물은 다음 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