34295번 - Rocky Mountain Road Trip 다국어

문제

Adeline and Byron are on a road trip through the mountains. Interestingly, the roads through the mountains can be modeled as a grid of size $ n \times m ,ドル where each cell has an integer altitude. The grid follows standard Cartesian coordinates, with the top-left corner being $ (1,1) $ and the bottom-right corner being $ (n, m) $.

Adeline, an adrenaline junkie, loves the ups and downs of the mountains, while Byron gets motion sick easily. After some debate, they agreed on a compromise: they must find a route from their starting position $ (x_0, y_0) $ to their destination $ (x_f, y_f) $ that minimizes the total distance traveled, but to make it fun for Adeline, they must alternate between gaining and losing altitude with every move. If they take a longer path than necessary, Byron will get sick.

Adeline and Byron's car can move in any of the 8 cardinal directions: North, Northeast, East, Southeast, South, Southwest, West, and Northwest. Each movement to an adjacent cell counts as a distance of 1, regardless of direction.

Help Adeline and Byron determine the minimum number of moves required to reach their destination.

입력

The first line contains two integers $ n $ and $ m $ $(1 \leq n, m \leq 500)$—the dimensions of the grid.

The next $ n $ lines each contain $ m $ integers $ h_{i,j} $ $(0 \leq h_{i,j} \leq 10^9),ドル representing the altitude of each cell in the grid.

The next line contains four integers $ x_0, y_0, x_f, y_f $ $(1 \leq x_0, x_f \leq n, 1 \leq y_0, y_f \leq m)$—the starting and destination positions.

It is guaranteed that the starting and destination positions are distinct.

출력

Print a single integer—the minimum number of moves required to reach $ (x_f, y_f) $ from $ (x_0, y_0) ,ドル or print $-1$ if it is impossible to reach the destination.

제한

힌트