华为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 roots = new ArrayList<>();
        Queue 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 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;
    }
}