华为od（D卷）亲子游戏

题目描述

宝宝和妈妈参加亲子游戏，在一个二维矩阵(N*N)的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。

游戏规则是妈妈必须在最短的时间(每个单位时间只能走一步)到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。

请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果(优先考虑最短时间到达的情况下尽可能多拿糖果)。

输入描述

第一行输入为 N，N 表示二维矩阵的大小。 之后 N 行，每行有 N 个值，表格矩阵每个位置的值，其中:

• -3: 妈妈

• -2: 宝宝

• -1: 障碍

• ≥0 : 糖果数(0 表示没有糖果，但是可以走)

输出描述

输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行未无多余空格。

地图最大 50 * 50

示例1

输入：
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3

输出：
9

说明：
此地图有两条最短路径可到达宝宝位置，绿色线和黄色线都是最短路径6步，但黄色拿到的糖果更多，9个。

示例2

输入：
4
3 2 1 -3
-1 -1 1 1
1 1 -1 2
-2 1 -1 3

输出：
-1

说明：
此地图妈妈无法到达宝宝的位置。

思路

必须在最短的时间(每个单位时间只能走一步)到达宝宝的位置 ：
最短路径问题
图论最短路径总结：

• 无权图+单源： BFS
• 有权（正数）+单源：直接Dijkstra
• 有权（有负数）+单源：直接 Bellman-Ford
• 多源：直接 Floyd

最多拿到多少糖果(优先考虑最短时间到达的情况下尽可能多拿糖果):

最短路径可能存在多条，计算每条最短路径的糖果，选择最少的即可。

代码

public class Demo01 {//方向选择private static final int[][] dir = new int[][] {{0, -1},{0, 1},{1, 0},{-1, 0}};public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextInt()) {int n = in.nextInt();// 第几行int row = n;// 第几列int col = n;// 母亲位置Node mom = null;// 孩子位置Node son = null;// 邻接矩阵存储图数据int[][] area = new int[row][col];for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {area[i][j] = in.nextInt();if (area[i][j] == -3) {mom = new Node(i, j, -3);}if (area[i][j] == -2) {son = new Node(i, j, -2);}}}System.out.println(bfs(area, mom, son));}in.close();}// 返回糖果数量public static int bfs(int[][] grid, Node start, Node target) {// 存储多条最短路径的根节点List<Node> roots = new ArrayList<>();Queue<Node> queue = new LinkedList<>();queue.offer(start);// 节点是否访问过int[][] visited = new int[grid.length][grid[0].length];// 到达孩子节点boolean reachTarget = false;while (!queue.isEmpty()) {if (reachTarget){break;}for (int i = 0; i < queue.size(); i++) {Node node = queue.poll();int x = node.x;int y = node.y;// 到达孩子节点if (x == target.x && y == target.y) {roots.add(node);reachTarget = true;}// 注意：设置访问过的位置，最短路径要多条。visited[node.x][node.y] = 1;for (int j = 0; j < dir.length; j++) {int nextX = x + dir[j][0];int nextY = y + dir[j][1];if (!canGo(grid, visited, nextX, nextY)) {continue;}Node e = new Node(nextX, nextY, grid[nextX][nextY], node);queue.offer(e);}}}return maxCandy(roots);}// x , y的节点是否能够前往public static boolean canGo(int[][] grid, int[][] visited, int x, int y) {// x合法  y合法  没放问过  不是障碍if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && visited[x][y] == 0 && grid[x][y] != -1) {return true;} else {return false;}}//计算最大糖果public static int maxCandy(List<Node> roots) {int max = -1;for (Node root : roots) {//没走到宝宝if (root.value != -2) {continue;}int candy = 0;Node cur = root;while (cur != null) {if (cur.value > 0) {candy = candy + cur.value;}cur = cur.father;}max = Math.max(candy, max);}return max;}}class Node {// 第几行public int x;// 第几列public int y;// 值public int value;// 指向前一个节点public Node father;public Node(int x, int y, int value) {this.x = x;this.y = y;this.value = value;}public Node(int x, int y, int value, Node father) {this.x = x;this.y = y;this.value = value;this.father = father;}
}