OD统一考试(D卷)
分值: 200分
题解: Java / Python / C++
题目描述宝宝和妈妈参加亲子游戏,在一个二维矩阵(N*N)的格子地图上,宝宝和妈妈抽签决定各自的位置,地图上每个格子有不同的糖果数量,部分格子有障碍物。
游戏规则是妈妈必须在最短的时间(每个单位时间只能走一步)到达宝宝的位置,路上的所有糖果都可以拿走,不能走障碍物的格子,只能上下左右走。
请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果(优先考虑最短时间到达的情况下尽可能多拿糖果)。
输入描述第一行输入为 N,N 表示二维矩阵的大小。 之后 N 行,每行有 N 个值,表格矩阵每个位置的值,其中:
-3: 妈妈
-2: 宝宝
-1: 障碍
: 糖果数(0 表示没有糖果,但是可以走)
输出描述输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果,行未无多余空格。
备注
地图最大 50 * 50
示例1 输入:43 2 1 -31 -1 1 11 1 -1 2-2 1 2 3输出:9说明:此地图有两条最短路径可到达宝宝位置,绿色线和黄色线都是最短路径6步,但黄色拿到的糖果