P2385 [USACO07FEB] Bronze Lilypad Pond B

为了让奶牛们娱乐和锻炼，农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了 $M$ 行 $N$ 列个方格（$1 \leq M,N \leq 30$）。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。 贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。 贝西的舞步很像象棋中的马步：每次总是先横向移动 $M_1 (1 \leq M_1 \leq 30)$ 格，再纵向移动 $M_2 (1 \leq M_2 \leq 30, M_1 ≠ M_2)$ 格，或先纵向移动 $M_1$ 格，再横向移动 $M_2$ 格。最多时，贝西会有八个移动方向可供选择。 给定池塘的布局和贝西的跳跃长度，请计算贝西从起点出发，到达目的地的最小步数，我们保证输入数据中的目的地一定是可达的。

第一行：四个用空格分开的整数：$M,N,M_1$ 和 $M_2$ 第二行到 $M + 1$ 行：第 $i + 1$ 行有 $N$ 个用空格分开的整数，描述了池塘第 $i$ 行的状态：`0` 为水，`1` 为莲花，`2` 为岩石，`3` 为贝西所在的起点，`4` 为贝西想去的终点。

第一行：从起点到终点的最少步数。