P5700 [CTSC1998] 罗杰游戏

CTSC1998 D2T1

罗杰游戏由一张棋盘和罗杰构成。棋盘由很多个小格组成，每个小格上刻有一个数字。其为 $-1$ 或 $0$ 至 $255$ 之间的一个数。罗杰是一个立方体，有六个面，每个面上分别有一个 $1$ 至 $6$ 之间的数字。 我们开始时把罗杰放在棋盘中的一个小格上，然后让其向前、后、左、右四个方向**翻滚**至邻近小格中。 游戏要求经过若干次翻滚后，让罗杰到达指定小格。 **罗杰不得进入标有 $-1$ 的小格，否则游戏结束**。 罗杰每进入一个小格后，将其顶面的数字同该小格的数字相乘，所得结果累加即得到罗杰的旅行费用。 开始时我们能看到罗杰的某些面上的数字，也可以指定当罗杰最终到达目的格时某些面上应出现的数字。对于**不确定的数字**，我们可以在**合法的基础上任意指定**。 **任务一** 罗杰只能向前或向右翻滚。 **任务二** 罗杰可以自由活动。

输入文件的第一行是数字 $1$ 或 $2$ 。表示是任务一还是任务二。 文件的第二行是两个整数 $M$ 和 $N$ ，给出了棋盘的列数和行数。 接下来的 $N$ 行每行表示棋盘的一行，有 $M$ 个数，依次给出了该行上每列的数。 其后的两行分别给出了罗杰的出发点信息和到达点信息。 每行开始的两个正整数给出了该格子的列号和行号。 接下来的六个数字分别表示了罗杰的顶，底，前、后、左、右各面的数字。 $0$ 表示可以任意指定。

输出文件的第一行给出罗杰的最小旅行费用。 如果罗杰不可能按要求到达目的地，则输出 $-1$ 。 否则其后每行给出罗杰的旅行情况： 从出发格到目的格，每行表示了罗杰的一个位置， 依次给出罗杰的当前旅行费用、所在格的列编号、行编号，以及罗杰6个面上的数字。 注意这时你的程序必须给出罗杰的完整信息，即各面上的数字不能为 $0$。

【数据范围】 $M \le 40$ , $N \le 40$ 。