[华为OD]C卷 BFS 亲子游戏 200

题目：

宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自

的位置，地图上每个格子有不同的Q糖果数量，部分格子有障碍物。

游戏规则Q是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的

所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。

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

可能多拿糖果）。

输入描述

第一行输入为N, N标识二维矩阵的大小

之后N行，每行有N个值，表格矩阵每个位置的值

其中：

- 3：妈妈

- 2：宝宝

- 1：障碍

> =0：糖果数（0表示没有糖果，但是可以走）

输出描述

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

备注

地图最大50*50

示例1：

输入

3 2 1 -3

1 -1 1 1

1 1 -1 2

-2 1 2 3

输出

说明

此地图有两条最短路径Q可到宝宝位置, 都是最短路径6步，但先向下再向左可以拿到9个糖

果

示例2：

输入

3 2 1 -3

-1 -1 1 1

1 1 -1 2

-2 1 -1 3

输出

-1

说明

此地图妈妈无法到达宝宝位置

题解：

图求最短路径，采用BFS搜索，关于BFS，推荐观看：BFS广搜解决迷宫问题_哔哩哔哩_bilibili

看完基本就清楚BFS算法原理了。

这题里面因为有糖果数目，所以这边采用的方法是，如果下一步能走到终点，那么终点位置的visit[endx][endy]不设置为1.这样其他方案走到终点的话，也能加入进队列里面。但是由于队列里面取首元素是终点的话，那么就不会往下找了，所以，搜索记录的应该也都是比较短的路线。然后再依旧采用一个List记录到终点的步数，一个Map记录到终点的步数和糖果数的结果。最后找到最少的步数，对应的最多糖果数就可以了。

代码：

import java.util.*;

public class FindCandy {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.valueOf(sc.nextLine());
        int nums[][] = new int[n][n];
        int stratPosX = Integer.MIN_VALUE;
        int stratPosY = Integer.MIN_VALUE;
        int childPosX = Integer.MIN_VALUE;
        int childPosY = Integer.MIN_VALUE;

        int visited[][] = new int[n][n];
        for (int i = 0; i < n; i++) {
            String path[] = sc.nextLine().split(" ");
            for (int j = 0; j < n; j++) {
                visited[i][j] = 0;
                nums[i][j] = Integer.valueOf(path[j]);
                if (nums[i][j] == -3) {
                    stratPosX = i;
                    stratPosY = j;
                    visited[i][j] = 1;
                }
                if (nums[i][j] == -2) {
                    childPosX = i;
                    childPosY = j;
                }
            }
        }

        int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        Queue<Steps> queue = new LinkedList<>();
        Steps firstStep = new Steps(stratPosX, stratPosY, 0, 0);
        visited[stratPosX][stratPosY] = 1;
        Steps endStep = new Steps(childPosX, childPosY, 0, 0);
        queue.offer(firstStep);

        List<Integer> finalRoteSteps = new ArrayList<>();
        Map<Integer, List<Integer>> stepCandyMap = new HashMap<>();
        boolean hasRoote = false;
        while (!queue.isEmpty()) {
            Steps frontStep = ((LinkedList<Steps>) queue).getFirst();
            if (frontStep.x == endStep.x && firstStep.y == endStep.y) {
                hasRoote = true;
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int newX = frontStep.x + directions[i][0];
                int newY = frontStep.y + directions[i][1];

                if (newX >= 0 && newX < n && newY >= 0 && newY < n && nums[newX][newY] != -1 && visited[newX][newY] == 0) {
//                    System.out.println("newX= " + newX + " newY " + newY + " candy " + nums[newX][newY]);
                    Steps nextStep = new Steps();
                    if (newX == endStep.x && newY == endStep.y) {
                        nextStep = new Steps(newX, newY, frontStep.getStep() + 1, frontStep.getCandy());
                        queue.offer(nextStep);
                        finalRoteSteps.add(nextStep.step);
                        List<Integer> candyList = stepCandyMap.containsKey(nextStep.step) ? stepCandyMap.get(nextStep.step) :
                                new ArrayList<>();
                        if (!candyList.contains(nextStep.candy)) {
                            candyList.add(nextStep.candy);
                        }
                        stepCandyMap.put(nextStep.step, candyList);
                        hasRoote = true;
                    } else {
                        nextStep = new Steps(newX, newY, frontStep.getStep() + 1, frontStep.getCandy() + nums[newX][newY]);
                        visited[newX][newY] = 1;
                        queue.offer(nextStep);
                    }
                }
            }
            ((LinkedList<Steps>) queue).pollFirst();
        }

        if (hasRoote) {
            Collections.sort(finalRoteSteps);
            List<Integer> candys = stepCandyMap.get(finalRoteSteps.get(0));
            Collections.sort(candys);
            System.out.println(candys.get(candys.size() - 1));
        } else {
            System.out.println(-1);
        }
    }
}

class Steps {
    int x;
    int y;
    int step;
    int candy;

    public Steps() {
    }

    public Steps(int x, int y, int step, int candy) {
        this.x = x;
        this.y = y;
        this.step = step;
        this.candy = candy;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    public int getStep() {
        return step;
    }

    public void setStep(int step) {
        this.step = step;
    }

    public int getCandy() {
        return candy;
    }

    public void setCandy(int candy) {
        this.candy = candy;
    }
}

验证：