브론즈: 연잎 연못

농부 존은 소들이 감상하고 운동할 수 있도록 직사각형 연못을 만들었다. 연못은 $M$개의 행과 $N$개의 열로 이루어진 격자로 나뉘어 있다 ($1 \le M \le 30$, $1 \le N \le 30$). 각 칸에는 세 가지 중 하나가 있다: 매우 튼튼한 연잎, 바위, 또는 그냥 물.

젖소 베시는 연잎에서 연잎으로 뛰어다니며 발레를 연습하고 있다. 지금 하나의 연잎 위에 서 있으며 다른 연잎으로 이동하려고 한다. 베시는 연잎에만 착지할 수 있고, 물이나 바위에는 착지할 수 없다.

베시의 각 도약은 일반화된 나이트(체스 말)의 이동 모양을 한다. 즉, 상하좌우 중 한 방향으로 $M_1$칸 이동한 뒤 그와 수직인 방향으로 $M_2$칸 이동하거나, $M_2$칸 이동한 뒤 수직인 방향으로 $M_1$칸 이동한다 ($1 \le M_1 \le 30$, $1 \le M_2 \le 30$, $M_1 \ne M_2$). 따라서 한 번의 도약에서 최대 여덟 개의 착지 후보 칸이 생긴다. 착지하는 칸만 연잎이면 되고, 도약 도중 지나가는 물이나 바위는 상관없다.

연못의 배치와 두 도약 길이가 주어질 때, 베시가 시작 연잎에서 도착 연잎까지 이동하는 데 필요한 최소 도약 횟수를 구하여라. 모든 입력에 대해 이동이 가능함이 보장된다.

첫째 줄에 네 정수 $M$, $N$, $M_1$, $M_2$가 공백으로 구분되어 주어진다.

다음 $M$개의 줄에는 각각 연못의 한 행을 나타내는 $N$개의 정수가 공백으로 구분되어 주어지며, 각 값의 의미는 다음과 같다.

• $0$ — 물
• $1$ — 연잎
• $2$ — 바위
• $3$ — 베시가 출발하는 연잎
• $4$ — 베시의 도착 연잎

값이 $3$인 칸과 값이 $4$인 칸은 각각 정확히 하나씩 존재한다.

베시가 시작 연잎에서 도착 연잎까지 이동하는 데 필요한 최소 도약 횟수를 정수 하나로 출력한다.

각 연잎을 그래프의 정점으로 생각하고, 두 연잎이 한 번의 일반화된 나이트 이동으로 이어질 때 간선을 잇는다. 그러면 시작 연잎에서의 너비 우선 탐색(BFS)으로 최소 도약 횟수를 구할 수 있다. 베시는 물이나 바위 위를 지나갈 수 있으며, 착지하는 칸만 연잎이면 된다는 점에 유의한다.