1. 小埋穿越迷宫
XJOI - 题目ID：6301必做题100分
最新提交：0 分
历史最高：0 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
小埋最近喜欢上了迷宫游戏，迷宫游戏是这样子的，首先该迷宫大小是 m∗nm∗n 的矩阵 gridgrid，矩阵下标从 00 开始，由从 00 到 m∗n−1m∗n−1 的不同整数组成。你可以在此单元格移动到下一行的任何其他单元格。在最后一行中的单元格不能触发移动。
每次可能的移动都需要付出对应的代价，代价用一个下标从 00 开始的二维数组 moveCostmoveCost 表示，该数组大小为(m∗n)∗n(m∗n)∗n，其中 moveCost[i][j]moveCost[i][j] 是从值为 ii 的单元格移动到下一行第 jj 列单元格的代价。从 gridgrid 最后一行的单元格移动的代价可以忽略。
迷宫的入口可以是第一行的任意一个位置，出口是最后一行的任意一个位置，现在小埋让你从中找到一条在迷宫从入口到出口的最小路径代价和。
gridgrid 一条路径的代价是：所有路径经过的单元格的 值之和 加上所有移动的 代价之和 。从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价。
输入格式
第一行输入一个整数 mm 和 nn,代表 gridgrid 矩阵的行和列。
接下来是 mm 行，每行输入 nn 个元素。
再接下来是 m∗nm∗n 行，每行输入 nn 个元素。
输出格式
每行输出一个整数，代表该迷宫从入口到出口的一个最小路径代价和。
样例
Input 1
2 3 5 1 2 4 0 3 12 10 15 20 23 8 21 7 1 8 1 13 9 10 25 5 3 2
Output 1
6
Input 2
3 2 5 3 4 0 2 1 9 8 1 5 10 12 18 6 2 4 14 3
Output 2
17
数据范围
2<=m,n<=502<=m,n<=50
gridgrid 由从 00 到 m∗n−1m∗n−1 的不同整数组成的
1<=moveCost[i][j]<=1001<=moveCost[i][j]<=100