Hosuk Saurus

Interview

Time limit1sMemory limit512 MB

Summary

A cow moves on a grid where allowed directions cycle with the move number (any, vertical only, horizontal only); find the minimum total cell shock from start to exit.

Level: Medium6 of 10
Topics: Graph, Shortest path, Dynamic programming, BFS
Solved: No attempts yet

Problem

Moo... Hosuk Saurus, a foolish cow, has no flexibility at all. He insists on escaping the maze stubbornly, exactly according to his own iron rule. The maze is an $N$ by $M$ grid, and each cell has a shock value that he takes the moment he enters it. If he enters the same room several times, he takes the same shock value each time. A smart cow would of course escape the maze while taking the least shock, or better yet would have used its head to avoid falling into the maze in the first place, but Hosuk Saurus has none of that!

His iron rule concerns how he moves. The directions he can move in differ for every move.

On the $3K$ -th move, he can move to one of the cells adjacent up, down, left, or right.
On the $3K+1$ -th move, he can move to one of the cells adjacent up or down.
On the $3K+2$ -th move, he can move to one of the cells adjacent left or right.
If there is a wall where he wants to move, he cannot move there.
The first move is move 1, followed by move 2, move 3, and so on.

Help Hosuk Saurus, who follows his iron rule but hates pain, and find the minimum total shock to reach the exit!

Input

The first line gives the grid dimensions $N$ and $M$ .

The second line gives the start and end positions $S\_x$ , $S\_y$ , $E\_x$ , $E\_y$ , separated by spaces. The start is at row $S\_x$ , column $S\_y$ , and the end is at row $E\_x$ , column $E\_y$ . The start and end are always different.

From the third line, $N$ lines give the map. Each line contains $M$ integers. The $j$ -th number on line $i+2$ is the shock value of the cell at row $i$ , column $j$ . If a shock value is $-1$ , that cell is a wall.

The shock values of the start and end are guaranteed to be 0.

Output

On the first line, print the minimum total shock Hosuk Saurus takes while escaping. If he cannot escape, print $-1$ .

Constraints

1 ≤ $N$ , $M$ ≤ 100
1 ≤ $S\_x, E\_x$ ≤ $N$
1 ≤ $S\_y, E\_y$ ≤ $M$
-1 ≤ shock value of each cell ≤ 300

Examples4

Example 1

Input

5 5
1 1 5 5
0 -1 1 -1 1
1 1 1 1 1
-1 1 1 1 1
1 1 -1 1 1
1 1 1 1 0

Expected output

Example 2

Input

4 4
1 1 1 4
0 1 1 0
1 1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1

Expected output

Example 3
Input
```
2 6
1 1 2 6
0 2 1 3 1 5
6 1 2 1 0 0
```
Expected output
```
14
```
Example 4
Input
```
4 2
3 1 1 1
0 -1
1 0
0 0
0 0
```
Expected output
```
1
```