### 华为OD机试C卷 - 亲子游戏（Java & JS & Python & C）
#### 题目背景与目标
本题目属于华为OD（Outsourcing Development）机试的一部分，旨在评估应试者对算法的理解与编程能力。具体而言，本题目要求应试者设计一个算法解决方案，用以计算在特定的游戏场景中，妈妈如何能在最短的时间内到达宝宝的位置，并且在此过程中收集尽可能多的糖果。
#### 题目描述详解
在一个由 N × N 的格子组成的二维矩阵中，妈妈和宝宝分别位于不同的位置。每个格子可能包含以下几种类型：
- **-3：** 表示妈妈的位置；
- **-2：** 表示宝宝的位置；
- **-1：** 表示不可通过的障碍物；
- **≥0：** 表示该格子含有的糖果数，0 表示没有糖果但可以通行。
游戏的目标是让妈妈尽快到达宝宝的位置，并在途中收集尽可能多的糖果。妈妈在每个单位时间内只能向上下左右中的任意一个方向移动一步，且不能穿过障碍物。需要计算出妈妈在最短到达宝宝位置的时间内最多能拿到多少糖果。
#### 输入输出格式
- **输入：**
- 第一行输入整数 N，表示矩阵的边长。
- 接下来的 N 行，每行 N 个整数，代表矩阵中各个位置的信息。
- **输出：**
- 输出一个整数，表示妈妈在最短到达宝宝位置的时间内最多能拿到的糖果数。
#### 题目解析
这个问题可以通过广度优先搜索 (BFS) 来解决。广度优先搜索是一种逐层探索图节点的算法，非常适合用来寻找最短路径问题。在这个题目中，我们首先将妈妈的位置加入队列中，然后依次从队列中取出每个位置，并检查其周围的四个相邻位置（上、下、左、右），如果某个相邻位置是可以到达的，则将其加入队列，并标记为已访问。此过程一直持续直到找到宝宝的位置为止。
#### 解决方案实现
下面分别给出 Java 和 Python 两种语言的具体实现：
##### Java 实现
```java
import java.util.*;
public class Main {
private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private static int N;
private static int[][] grid;
private static boolean[][] visited;
private static int maxCandies = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
N = scanner.nextInt();
grid = new int[N][N];
visited = new boolean[N][N];
int babyRow = -1, babyCol = -1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
grid[i][j] = scanner.nextInt();
if (grid[i][j] == -2) {
babyRow = i;
babyCol = j;
}
}
}
bfs(babyRow, babyCol);
System.out.println(maxCandies);
}
private static void bfs(int startRow, int startCol) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{startRow, startCol, 0, 0});
visited[startRow][startCol] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int row = current[0], col = current[1], time = current[2], candies = current[3];
if (grid[row][col] == -3) {
maxCandies = Math.max(maxCandies, candies);
continue;
}
for (int[] direction : DIRECTIONS) {
int newRow = row + direction[0], newCol = col + direction[1];
if (newRow >= 0 && newRow < N && newCol >= 0 && newCol < N
&& !visited[newRow][newCol] && grid[newRow][newCol] >= 0) {
visited[newRow][newCol] = true;
queue.offer(new int[]{newRow, newCol, time + 1, candies + grid[newRow][newCol]});
}
}
}
}
}
```
##### Python 实现
```python
from collections import deque
def bfs(n, grid):
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False] * n for _ in range(n)]
max_candies = 0
# 找到宝宝的位置
baby_row, baby_col = None, None
for i in range(n):
for j in range(n):
if grid[i][j] == -2:
baby_row, baby_col = i, j
break
# 广度优先搜索
queue = deque([(baby_row, baby_col, 0, 0)])
visited[baby_row][baby_col] = True
while queue:
row, col, time, candies = queue.popleft()
if grid[row][col] == -3:
max_candies = max(max_candies, candies)
continue
for dr, dc in directions:
newRow, newCol = row + dr, col + dc
if 0 <= newRow < n and 0 <= newCol < n and not visited[newRow][newCol] and grid[newRow][newCol] >= 0:
visited[newRow][newCol] = True
queue.append((newRow, newCol, time + 1, candies + grid[newRow][newCol]))
return max_candies
# 示例输入
n = 5
grid = [
[0, 2, 1, 0, 3],
[1, 0, 1, 0, -1],
[0, 0, 0, 0, 1],
[-1, 1, 0, 1, 1],
[-3, 0, 1, 0, 0]
]
print(bfs(n, grid))
```
通过以上两种语言的实现可以看出，无论采用哪种语言，核心思想都是使用广度优先搜索来解决问题。此外，本题还提供了 JavaScript 和 C 语言的解决方案，但由于篇幅限制，这里不再赘述。希望以上内容能够帮助读者理解本题目的算法思路及其实际应用。
