Optimizing the Modified Snake Game

You are given a modified snake game played on an R x C grid. Each cell \( A_{i,j} \) of the grid has an integer weight \( w(A_{i,j}) \) where \( 0\le w(A_{i,j})\le8 \). A cell with weight 0 is forbidden, and any cell with a positive weight is enterable.

The snake is represented by a sequence of cells \(B_1, B_2, \dots, B_m\) (initially \(m=4\)), where \(B_1\) is the head, and for each adjacent pair \(B_i\) and \(B_{i+1}\) (\(1\le i < m\)) they are neighbors in one of the four directions: left, right, up, or down. In addition, no two parts of the snake can occupy the same cell.

Some enterable cells contain food. Each food is located at a unique cell and can be eaten only once.

The snake can either move or eat in any of the four basic directions (left, right, up, down) provided that the destination cell is enterable. The time cost for a move (or eating action) from a cell \(P\) to a cell \(Q\) is

[ cost = |w(P)-w(Q)|+1. ]

Movement: When moving into an empty cell, the snake’s head moves into \(Q\) while the rest of the body shifts forward and the tail cell is removed. Note that it is allowed for the new head to move into the old tail cell because the tail is removed in the same move.

Eating: If the destination cell \(Q\) contains food, the snake eats it and its length increases by 1; in this case, after moving, the tail does not move. In either case, after the move the snake’s new shape (the ordered list of cells) must satisfy the adjacent cell constraints and non-overlapping condition.

The initial configuration (including the snake’s starting 4 cells and all food positions) is given. Your task is to compute the minimum total time for the snake to eat all the food items.

inputFormat

The input is given as follows:

R C
A[1,1] A[1,2] ... A[1,C]
A[2,1] A[2,2] ... A[2,C]
...
A[R,1] A[R,2] ... A[R,C]
x1 y1
x2 y2
x3 y3
x4 y4
F
f1_x f1_y
f2_x f2_y
...
fF_x fF_y

</p>

Here, the first line contains two integers \(R\) and \(C\). The next \(R\) lines each contain \(C\) integers describing the grid weights. Then 4 lines follow, each with two integers, representing the coordinates of the snake's parts (from head to tail). After that, an integer \(F\) denotes the number of food items, followed by \(F\) lines each containing the coordinates of a food cell.

All coordinates are 1-indexed.

outputFormat

Output a single integer representing the minimum total time required for the snake to eat all the food items. If it is impossible, output -1.

sample

3 3
1 1 1
1 0 1
1 1 1
1 1
1 2
2 2
3 2
1
3 3

6

</p>