亲子游戏 od 算法题

### 华为OD机试算法题目——亲子游戏 #### 问题描述 在一个 \( N \times N \) 的二维矩阵中，宝宝和妈妈通过抽签决定各自的位置。地图上的每个格子可能含有不同数量的糖果或障碍物。具体来说： - `>=0` 表示该处拥有的糖果数目。 目标是在最短时间内让妈妈找到宝宝，并计算在此过程中能收集的最大糖果数[^4]。 #### 解决方案概述 为了求解此问题，可以采用广度优先搜索 (BFS)，因为 BFS 能够有效地探索所有可能路径并记录最小步数下的最优解。对于每一个节点，除了保存当前坐标外还需要跟踪已获得的糖果总数以及移动次数。当首次抵达终点时即得到全局最优解。 #### Python实现代码 下面给出了一种基于队列的数据结构来执行标准宽度遍历的方法: ```python from collections import deque def max_candies(matrix, n): directions = [(0, 1), (1, 0), (-1, 0), (0, -1)] start_pos = None end_pos = None for i in range(n): for j in range(n): if matrix[i][j] == -3: start_pos = (i, j) elif matrix[i][j] == -2: end_pos = (i, j) queue = deque([(start_pos[0], start_pos[1], 0)]) visited = set([start_pos]) candies_collected = {start_pos: matrix[start_pos[0]][start_pos[1]]} while queue: x, y, steps = queue.popleft() if (x, y) == end_pos: return candies_collected[(x, y)] + 2 for dx, dy in directions: nx, ny = x + dx, y + dy if not (0 <= nx < n and 0 <= ny < n): continue next_cell_value = matrix[nx][ny] if next_cell_value >= -2 and (nx, ny) not in visited: new_candy_count = candies_collected.get((x,y)) or 0 if next_cell_value != -1: candies_collected.update({(nx, ny):new_candy_count + next_cell_value}) visited.add((nx, ny)) queue.append((nx, ny, steps + 1)) return -1 ``` 上述程序首先定位起点(`-3`) 和 终点 (`-2`) ，接着利用队列来进行层次化扩展直到遇到第一个匹配的目标位置为止；期间累积经过单元格内的正整数值作为获取到的糖分数量总和。如果最终未能触及目的地，则返回 `-1` 表明不存在可行路线。