Description

To entertain and exercise the cows, Farmer John built a beautiful pond. This rectangular pond is divided into $M$ rows and $N$ columns ($1 \le M, N \le 30$). Some cells are surprisingly sturdy lilypads, some are rocks, and the rest are beautiful, pure, deep-blue water.

Bessie is practicing ballet. She stands on a lilypad and wants to jump to another lilypad. She can only jump from a lilypad to another lilypad; she cannot jump onto water or rocks.

Bessie’s steps are like a knight’s moves in chess: each time she either moves horizontally $M_1$ squares ($1 \le M_1 \le 30$) and then vertically $M_2$ squares ($1 \le M_2 \le 30$, $M_1 \ne M_2$), or vertically $M_1$ squares and then horizontally $M_2$ squares. At most, Bessie has eight possible movement directions.

Given the pond layout and Bessie’s jump lengths, compute the minimum number of jumps needed for Bessie to go from the start to the destination. It is guaranteed that the destination in the input is reachable.

Input Format

The first line contains four space-separated integers: $M$, $N$, $M_1$, and $M_2$.

The second line through line $M+1$: for each $i$ from $1$ to $M$, line $i+1$ contains $N$ space-separated integers describing row $i$ of the pond: $0$ for water, $1$ for lilypad, $2$ for rock, $3$ for Bessie’s starting cell, and $4$ for Bessie’s destination.

Output Format

The first line contains the minimum number of moves from the start to the destination.

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

2

Hint

Translated by ChatGPT 5