一、【广度优先搜索（BFS）算法】_亲子游戏

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

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

请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。
知识点：[广搜]

分析：这个问题涉及到路径规划和最短路径问题。可以使用广度优先搜索（BFS）来解决这个问题，因为BFS适合用来找到最短路径，特别是在没有权重的情况下（每一步的代价是一样的，即步数）。
思路：使用BFS算法在一个二维矩阵上找到从妈妈到宝宝的最短路径，并计算沿途可以收集的糖果数量。其核心思想是利用队列存储待访问的节点，逐层遍历每个可能的路径，同时利用visited数组确保不重复访问，最终返回可收集的最大糖果数量。

用c语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>#define N 5 // 假设地图是一个5*5的矩阵，可以根据实际情况修改N的值// 定义方向数组，表示上下左右四个方向的移动
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 定义一个结构体表示坐标
typedef struct {int x;int y;
} Point;// BFS搜索函数
int bfs(int grid[N][N], Point start, Point end) {// 创建队列用于BFSPoint queue[N * N];bool visited[N][N];int front = 0, rear = 0;// 初始化队列和访问标记queue[rear++] = start;visited[start.x][start.y] = true;// 初始化糖果总数int total_candies = 0;// BFS主循环while (front < rear) {Point current = queue[front++];// 到达目标点，返回总糖果数if (current.x == end.x && current.y == end.y) {return total_candies;}// 遍历四个方向for (int i = 0; i < 4; ++i) {int nx = current.x + directions[i][0];int ny = current.y + directions[i][1];// 检查边界和障碍物if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && grid[nx][ny] != -1) {// 标记访问visited[nx][ny] = true;// 更新队列queue[rear++] = (Point){nx, ny};// 累加糖果total_candies += grid[nx][ny];}}}// 如果没有找到路径，返回0return 0;
}// 主函数
int main() {int grid[N][N] = {{2, 1, 0, 2, -1},{1, 0, 1, 1, 1},{1, 1, 0, 0, 1},{0, 1, 1, 0, 1},{1, 0, 1, 1, 2}};// 假设宝宝和妈妈的位置Point baby = {0, 0}; // 宝宝的位置Point mom = {4, 4};  // 妈妈的位置// 调用BFS函数获取最大糖果数int max_candies = bfs(grid, mom, baby);// 输出结果printf("最多可以拿到的糖果数量为：%d\n", max_candies);return 0;
}

在这段代码中：
 grid数组表示地图，其中-1表示障碍物，非负数表示格子上的糖果数量。
b fs函数使用BFS算法找到从妈妈位置到宝宝位置的最短路径，并计算沿途可以拿到的总糖果数。
 主函数中定义了一个示例的5*5地图和宝宝、妈妈的初始位置，调用bfs函数计算出最大可以拿到的糖果数量，并输出结果。

1、头文件和宏定义

在这段代码中：
· 头文件：stdio.h用于输入输出，stdlib.h用于动态内存管理，stdbool.h用于使用布尔类型，limits.h用于获取整数的极限值。
· 宏定义：#define N 5定义了地图的大小，设置为5x5。可以根据需要调整。

2、方向数组定义

int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

方向数组：这个数组表示上下左右四个可能的移动方向。

{-1, 0} 表示向上移动
{1, 0} 表示向下移动
{0, -1} 表示向左移动
{0, 1} 表示向右移动

3、坐标结构体定义

typedef struct { int x; int y; } Point;

Point结构体：用于存储坐标的结构体，包含两个成员x和y，分别表示二维矩阵中的行和列。

4.BFS搜索函数

int bfs(int grid[N][N], Point start, Point end) {Point queue[N * N];bool visited[N][N];int front = 0, rear = 0;queue[rear++] = start;visited[start.x][start.y] = true;int total_candies = 0;

· 函数参数：
grid[N][N]：二维矩阵，表示地图。
Point start：妈妈的起始位置。
Point end：宝宝的位置。

· BFS数据结构：
queue[N * N]：用于存储待访问的节点。
visited[N][N]：布尔数组，用于标记节点是否已访问。

· 初始化：
将起始位置加入队列，并标记为已访问。
total_candies用于累积在路径上收集的糖果。

5.BFS主循环

while (front < rear) {Point current = queue[front++];if (current.x == end.x && current.y == end.y) {return total_candies;}for (int i = 0; i < 4; ++i) {int nx = current.x + directions[i][0];int ny = current.y + directions[i][1];if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && grid[nx][ny] != -1) {visited[nx][ny] = true;queue[rear++] = (Point){nx, ny};total_candies += grid[nx][ny];}}
}

· 循环：
当队列不为空时，循环取出当前节点（current）。
检查是否到达宝宝的位置，如果到达，返回累积的糖果数。

· 遍历四个方向：
计算下一个可能的坐标(nx, ny)。
检查坐标是否在边界内、未访问且不是障碍物。
如果条件满足，标记为已访问，加入队列，并更新糖果总数。

6.主函数

int main() {int grid[N][N] = {{2, 1, 0, 2, -1},{1, 0, 1, 1, 1},{1, 1, 0, 0, 1},{0, 1, 1, 0, 1},{1, 0, 1, 1, 2}};Point baby = {0, 0}; // 宝宝的位置Point mom = {4, 4};  // 妈妈的位置int max_candies = bfs(grid, mom, baby);printf("最多可以拿到的糖果数量为：%d\n", max_candies);return 0;
}

· 地图定义：一个5x5的地图，具体数值表示每个格子的糖果数量，-1表示障碍物。

· 位置定义：
Point baby = {0, 0}：宝宝的位置。
Point mom = {4, 4}：妈妈的位置。
· 调用BFS函数：计算从妈妈位置到宝宝位置的最大糖果数，并输出结果。

彩蛋：

涉及算法：BFS
广度优先搜索（BFS）算法，旨在找到从妈妈的位置到宝宝位置的最短路径，并在此路径上累积糖果数量。

BFS函数分析

函数签名

int bfs(int grid[N][N], Point start, Point end) {

参数：

int grid[N][N]：二维矩阵，表示游戏地图，每个格子包含糖果数量或障碍物信息。
Point start：妈妈的起始位置。
Point end：宝宝的位置。

返回值：返回沿最短路径上可以收集的最大糖果数量。

变量定义与初始化:

Point queue[N * N];bool visited[N][N];int front = 0, rear = 0;queue[rear++] = start;
visited[start.x][start.y] = true;
int total_candies = 0;

队列：Point queue[N * N] 用于存储待访问的坐标点，队列的最大容量为 N * N。
访问标记：bool visited[N][N] 用于标记每个格子是否已经被访问过，防止重复遍历。
队列指针：int front 和 int rear 分别表示队列的前端和后端，用于插入和移除元素。
初始化队列：将妈妈的起始位置加入队列，并标记为已访问。
糖果计数：int total_candies = 0 初始化沿路径可收集的糖果数量为0。

BFS主循环

while (front < rear) {Point current = queue[front++];if (current.x == end.x && current.y == end.y) {return total_candies;}

循环条件：while (front < rear)，只要队列不为空，就继续循环。
取出当前点：Point current = queue[front++] 从队列中取出前面的坐标点，并更新队列前端指针。
检查目标：如果当前坐标与宝宝的位置相同，直接返回当前累积的糖果数量。

遍历四个方向

for (int i = 0; i < 4; ++i) {int nx = current.x + directions[i][0];int ny = current.y + directions[i][1];if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && grid[nx][ny] != -1) {visited[nx][ny] = true;queue[rear++] = (Point){nx, ny};total_candies += grid[nx][ny];}
}

遍历方向：使用 for 循环遍历四个可能的移动方向。

int nx = current.x + directions[i][0]：计算下一个位置的x坐标。
int ny = current.y + directions[i][1]：计算下一个位置的y坐标。

检查边界和条件：

if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && grid[nx][ny] != -1)：

确保新位置 nx 和 ny 在矩阵边界内。
确保该位置未被访问过（!visited[nx][ny]）。
确保该位置不是障碍物（grid[nx][ny] != -1）。

更新状态：

visited[nx][ny] = true：标记新位置为已访问。
queue[rear++] = (Point){nx, ny}：将新位置加入队列。
total_candies += grid[nx][ny]：将新位置的糖果数量加入总糖果数。

结束条件
return 0;
如果队列遍历完毕，仍未找到宝宝的位置，返回0，表示没有找到路径。

总结
这个 bfs 函数通过广度优先搜索算法有效地探索了从妈妈位置到宝宝位置的路径。关键步骤包括：

1. 使用队列实现层次遍历，确保最短路径的探索。
2. 通过访问标记避免重复遍历，确保算法的效率。
3. 累计糖果数量，在到达目标位置时返回该数量。