Background

CTSC1998 D2T1.

Problem Description

The Roger Game consists of a board and Roger. The board is made up of many small cells, and each cell has a number engraved on it. This number is either $-1$ or an integer between $0$ and $255$. Roger is a cube with six faces, and each face has a number from $1$ to $6$.

At the beginning, we place Roger on a cell on the board, and then let it roll forward, backward, left, or right into an adjacent cell.

The game requires that after several rolls, Roger reaches a specified target cell.

Roger must not enter a cell marked $-1$, otherwise the game ends.

Each time Roger enters a cell, multiply the number on its top face by the number in that cell, and add the result to the total. This total is Roger's travel cost.

At the start, we can see the numbers on some faces of Roger. We may also specify that when Roger finally reaches the target cell, some faces should show certain numbers. For unspecified numbers, we may assign them arbitrarily as long as it is valid.

Task 1

Roger can only roll forward or to the right.

Task 2

Roger can move freely.

Input Format

The first line of the input file is the number $1$ or $2$, indicating Task 1 or Task 2.

The second line contains two integers $M$ and $N$, giving the number of columns and the number of rows of the board.

The next $N$ lines each describe one row of the board, containing $M$ numbers, giving the numbers of the cells in that row from left to right.

The following two lines give the information for Roger's start cell and target cell, respectively.

Each line begins with two positive integers giving the column index and row index of that cell.

The next six numbers represent the numbers on Roger's top, bottom, front, back, left, and right faces. A $0$ means it can be assigned arbitrarily.

Output Format

The first line of the output file should give Roger's minimum travel cost.

If it is impossible for Roger to reach the target as required, output $-1$.

Otherwise, output the travel process, one line per position from the start cell to the target cell.

Each line should contain, in order: the current total travel cost, the column index, the row index, and the numbers on Roger's 6 faces.

Note that your program must output Roger's complete information at this time, i.e. none of the face numbers may be $0$.

2 
10 10
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1
1 1 1 9 8 7 6 5 4 1
1 1 9 8 7 6 5 4 1 1
1 1 8 7 6 5 4 1 1 1
1 1 7 6 5 4 1 1 1 1
1 1 6 5 4 1 1 1 1 1
1 1 5 4 1 1 1 1 1 1
1 1 4 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
3 3 0 0 0 0 0 0
8 8 0 0 0 0 0 0

44
0 3 3 6 5 3 1 2 4
3 3 2 3 1 5 6 2 4
5 4 2 2 4 5 6 1 3
6 5 2 1 3 5 6 4 2
10 6 2 4 2 5 6 3 1
13 7 2 3 1 5 6 2 4
15 8 2 2 4 5 6 1 3
16 9 2 1 3 5 6 4 2
20 10 2 4 2 5 6 3 1
26 10 3 6 5 4 2 3 1
28 10 4 2 4 6 5 3 1
29 9 4 1 3 6 5 2 4
34 9 5 5 6 1 3 2 4
38 8 5 4 2 1 3 5 6
41 8 6 3 1 4 2 5 6
43 8 7 2 4 3 1 5 6
44 8 8 1 3 2 4 5 6

Hint

【Constraints】

$M \le 40$ , $N \le 40$ 。

Translated by ChatGPT 5