1370번 - 전쟁 - 화계가 아닌 수계

화계라는 것은 불로써 적을 공격하는 계략을 이야기한다. 예를 들자면, 적벽대전에서 바람의 방향을 이용해서 조조군의 방심을 이용했다는 제갈량의 지혜처럼, 화계라는 것은 전쟁에 사용되면 매우 좋은 효과를 본다는 것 만은 확실하다고 알 수 있다. 물론, 그것을 사용하기에는 여러 가지 제약이 따르지만.

요컨데, 불로는 사람을 죽이기 쉽다는 소리다.

그래서 당신은 적군이 있는 곳에 불을 지르려 했다.

그런데 웬걸, 적군은 우리가 화계를 쓸 줄 알고 나무가 없는 곳에 진을 쳤다는 사실을 알았다!

그렇다면 어떻게 해야 할까? 그래. 수계를 쓰자.

N*N크기의 맵이 있다. 적군은 (x,y)에 있고, 우리는 1,1에서 물을 흘린다. 만약 어떤 곳에 물이 있다고 가정하자. 그런데 네 방향중에 더 낮은 (물로 채워진 높이 포함) 곳이 있다면, 그곳을 향해 물이 흐른다.

물은 안정화가 될 때 까지 흐르게 된다. (안정화라는 말은, 어떠한 위치의 물도 다른 방향으로 흐르지 않는다는 의미이다.)

당신은 적군이 있는 곳에 높이 k이상의 물을 채우기 위해서는 얼마의 물이 필요한지 계산하는 것이다.

첫째 줄에는 문제에서 맵의 크기를 나타내는 정수 N(<=400)과 적군이 있는 곳에 채워야 되는 물의 높이 k(<=1,000,000)가 주어진다. 두 번째 줄에는 적군이 있는 위치 x y가 주어진다. 세 번째 줄에서 N+2번째 줄에는 각각 땅이 파여져 있는 깊이가 주어진다. 깊이의 양은 1,000,000을 넘지 않는다.

흘려야 되는 물의 양을 출력한다.

7의 물을 흘리면, 1,1에 5의 물이 채워지고, 5,4에 2의 물이 채워지게 된다. 물을 흘렸을 때 안정화 될 수 있는 상태가 여러개 있다면, 우리는 그 중에서 어떤 상태가 될지 알 수 없으므로 확실하게 적군이 k높이만큼 잠기는 최소 물의 양을 출력해야 한다. 물이 N*N맵 밖으로 빠져나가는 경우는 없다고 봐도 무방하다.