물 뿌리기

대학원생인 당신은 현재 $N \times N$ 격자 부지에서 물의 흐름을 연구하고 있다. 목표는 높이가 주어진 $N^2$개의 칸 중 물이 닿는 칸이 몇 개인지 알아내는 것이다. 수년간의 연구 끝에 물이 다음 규칙에 따라 확산한다는 것을 알아냈다.

• 각 칸의 물 상태는 $0, 1, 2, \cdots, X$의 $(X+1)$개 정수 중 하나이다. $0$은 물이 없는 상태이고, $1, \cdots, X$는 물이 있는 상태이다.
• 처음 물을 뿌린 칸의 물 상태는 $X$이다.
• 칸 $(x,y)$에서 인접한 칸으로 물이 확산해도 $(x,y)$의 물 상태는 바뀌지 않는다.
• $1$보다 큰 정수 $l$에 대하여, 물 상태가 $l$인 칸의 물은 다음 규칙에 따라 확산한다.
  • 매초, 현재 칸과 높이가 같은 인접 칸으로 물이 확산한다. 확산한 물의 상태는 $(l-1)$이다. 단, 상태가 $(l-1)$ 이상인 칸으로는 물이 확산하지 않는다.
  • 매초, 현재 칸보다 높이가 낮은 인접 칸으로 물이 확산한다. 확산한 물의 상태는 $X$이다.
• 한 칸에서 물이 여러 번 확산할 수 있다. 모든 칸에서 확산은 동시에 일어난다.
• 여러 칸에서 한 칸으로 동시에 물이 확산하면, 그 칸의 물 상태는 확산한 물 상태 중 최댓값이다.
• 칸 $(x,y)$의 물 상태가 $0$이고 어떤 칸에서도 $(x,y)$로 물이 확산하지 않으면, $(x,y)$의 물 상태는 $0$이다.

두 칸 $(a,b)$와 $(x,y)$가 서로 인접한다는 것은 $|a-x|+|b-y| = 1$임을 뜻한다. $(i,j)$는 $i$행 $j$열을 가리킨다. $N \times N$ 격자의 각 칸 높이와 물을 처음 뿌린 위치가 주어질 때, 물이 더 이상 확산하지 않을 만큼 충분히 시간이 지난 뒤 물이 있는 칸, 즉 물 상태가 $1, \cdots, X$인 칸의 수를 구하시오.

첫 줄에 네 정수 $N$, $X$, $x$, $y$가 공백으로 구분되어 주어진다. ($1 \le N \le 2\,000$, $1 \le X \le 2N$, $1 \le x, y \le N$)

$N$은 격자의 한 변 길이, $X$는 처음 뿌려진 물의 상태, $(x,y)$는 처음 물을 뿌린 위치이다.

두 번째 줄부터 $N$개의 줄에 격자 부지가 주어진다. $i$번째 줄의 $j$번째 정수 $h_{ij}$는 $(i,j)$의 높이이다. ($0 \le h_{ij} \le 100\,000$)

물이 더 이상 확산하지 않을 만큼 충분히 시간이 지난 뒤, 물이 있는 칸(물 상태가 $1, \cdots, X$인 칸)의 수를 첫 줄에 출력한다.