题一：亲子游戏_bfs亲子游戏

题目

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

         游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。 请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。

思路

        广度优先搜索算法（BFS），Dijkstra算法

题解  

import java.util.*;
 
// 定义一个Point类来表示每个点的位置、糖果数量和步数
class Point {
    int x, y, candy, step;
 
    public Point(int x, int y, int candy, int step) {
        this.x = x;
        this.y = y;
        this.candy = candy;
        this.step = step;
    }
}
 
public class CandyGame {
    // 定义四个方向，分别是上、下、左、右
    private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
 
    public int maxCandy(int[][] grid, Point mom, Point baby) {
        int n = grid.length;
        // 创建一个二维布尔数组来记录每个点是否被访问过
        boolean[][] visited = new boolean[n][n];
        // 创建一个队列用于广度优先搜索
        Queue<Point> queue = new LinkedList<>();
        // 设置妈妈的初始糖果数量和步数
        mom.candy = grid[mom.x][mom.y];
        mom.step = 0;
        // 将妈妈的位置添加到队列中
        queue.offer(mom);
 
        // 当队列不为空时，继续搜索
        while (!queue.isEmpty()) {
            // 从队列中取出一个点
            Point current = queue.poll();
            // 如果这个点是宝宝的位置，那么返回这个点的糖果数量
            if (current.x == baby.x && current.y == baby.y) {
                return current.candy;
            }
 
            // 遍历当前点的四个方向
            for (int[] direction : DIRECTIONS) {
                // 计算新的位置
                int newX = current.x + direction[0];
                int newY = current.y + direction[1];
 
                // 如果新的位置在矩阵内，且没有被访问过，且没有障碍物
                if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY] && grid[newX][newY] != -1) {
                    // 标记这个位置已经被访问过
                    visited[newX][newY] = true;
                    // 将这个位置添加到队列中，并更新糖果数量和步数
                    queue.offer(new Point(newX, newY, current.candy + grid[newX][newY], current.step + 1));
                }
            }
        }
 
        // 如果没有找到到达宝宝的路径，那么返回-1
        return -1;
    }
}

扩展

        广度优先搜索（Breadth-First Search，简称BFS）是一种用于遍历或搜索树或图的算法。这个算法从图的某一节点（或树的根）开始，然后访问所有相邻的节点，然后对每个相邻节点，再访问它们的未被访问过的邻节点，以此类推，直到图中所有节点都被访问过。

        广度优先搜索的主要特点是“先宽后深”，即先访问当前节点的所有邻节点，再访问这些邻节点的邻节点。因此，广度优先搜索可以找到从起始节点到其他所有节点的最短路径。

        广度优先搜索通常使用队列来实现。在搜索过程中，首先将起始节点放入队列，然后重复以下步骤直到队列为空：从队列中取出一个节点，访问这个节点，然后将这个节点的所有未被访问过的邻节点放入队列。

        广度优先搜索在许多领域都有应用，例如在图的遍历、寻找最短路径、网络爬虫、社交网络分析等方面都有广泛的应用。

扩展2

        在这个问题中，我们的目标是找到从妈妈到宝宝的最短路径，并在这个路径上获取最多的糖果。因此，我们首先需要找到最短的路径，然后在这些最短的路径中找到糖果最多的那一条。在广度优先搜索中，我们总是先访问距离起始点更近的点，再访问距离起始点更远的点。因此，当我们找到宝宝的位置时，我们找到的路径一定是最短的路径。如果有多条最短的路径，我们会在这些路径中找到糖果最多的那一条。

         如果有两条最短的路径，一条糖果更多，一条糖果更少，但是糖果更少的那条路径先被遍历到，那么上面的算法会返回糖果更少的那条路径。这是因为我们的算法在找到宝宝的位置后就会立即停止搜索，而不会继续寻找其他可能的路径。

        如果我们希望在所有最短的路径中找到糖果最多的那一条，我们需要修改我们的算法。一种可能的方法是使用Dijkstra算法，并将糖果数量作为路径的权重。这样，我们可以在找到所有最短的路径后，选择糖果最多的那一条。

import java.util.*;
 
class Point {
    int x, y, candy, step;
 
    public Point(int x, int y, int candy, int step) {
        this.x = x;
        this.y = y;
        this.candy = candy;
        this.step = step;
    }
}
 
public class CandyGame {
    private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
 
    public int maxCandy(int[][] grid, Point mom, Point baby) {
        int n = grid.length;
        Point[][] points = new Point[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                points[i][j] = new Point(i, j, grid[i][j], Integer.MAX_VALUE);
            }
        }
 
        PriorityQueue<Point> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.step));
        mom.step = 0;
        queue.offer(mom);
 
        while (!queue.isEmpty()) {
            Point current = queue.poll();
            if (current.x == baby.x && current.y == baby.y) {
                return current.candy;
            }
 
            for (int[] direction : DIRECTIONS) {
                int newX = current.x + direction[0];
                int newY = current.y + direction[1];
 
                if (newX >= 0 && newX < n && newY >= 0 && newY < n && grid[newX][newY] != -1) {
                    Point next = points[newX][newY];
                    int newCandy = current.candy + next.candy;
                    int newStep = current.step + 1;
                    if (newStep < next.step || newStep == next.step && newCandy > next.candy) {
                        next.candy = newCandy;
                        next.step = newStep;
                        queue.offer(next);
                    }
                }
            }
        }
 
        return -1;
    }
}

扩展3: 

         Dijkstra算法是一种用于在图中找到从一个节点到所有其他节点的最短路径的算法。这个算法由荷兰计算机科学家艾兹格·迪科斯彻在1956年发明。

        Dijkstra算法的基本思想是每次找到离起始点最近的一个节点，然后更新这个节点的所有邻节点的距离。这个过程会重复进行，直到所有的节点都被访问过。

Dijkstra算法的步骤如下：
        1. 创建一个集合，用于存储已经被访问过的节点。
        2. 将起始节点的距离设为0，将所有其他节点的距离设为无穷大。
        3. 对于每一个未被访问过的节点，找到距离最小的节点，将其添加到已访问的节点集合中。
        4. 更新这个节点的所有邻节点的距离。如果通过这个节点到达邻节点的距离小于当前的距离，那么就更新这个距离。
        5. 重复步骤3和4，直到所有的节点都被访问过。

        Dijkstra算法在许多领域都有应用，例如在网络路由、地图导航、社交网络分析等方面都有广泛的应用。