1. 项目背景与核心需求
图书馆里的老鼠这个题目乍看有些无厘头，但作为GESP一级编程考题，它实际上考察的是基础的逻辑思维和编程能力。题目通常会描述一只老鼠在图书馆中寻找食物的过程，需要考生通过编程模拟老鼠的移动路径或解决相关问题。
这类题目在青少年编程教育中非常典型，它用生动有趣的场景包装了基础的编程概念。我见过很多类似的题目变体，比如"迷宫中的机器人"、"森林里的小兔子"等等。这种设计能有效降低初学者的心理门槛，让编程学习变得更有趣味性。
2. 题目分析与解题思路
2.1 题目场景拆解
假设题目描述如下：图书馆被建模为一个M×N的网格，某些格子放着书（障碍物），老鼠需要从起点移动到终点获取奶酪。考生需要编写程序计算老鼠的最短路径或可行路径数量。
这类题目通常会考察以下几个编程基础概念：
- 二维数组的表示与遍历
- 基本的搜索算法（深度优先或广度优先）
- 简单的条件判断和循环结构
- 基础的问题分解能力
2.2 解题方法选择
对于一级考生，最合适的解法是使用广度优先搜索(BFS)。相比深度优先搜索(DFS)，BFS更容易理解和实现，也更适合找最短路径问题。虽然DFS也能解决问题，但对于初学者来说，递归的实现方式可能更具挑战性。
BFS的核心思路是：
- 使用队列记录待访问的位置
- 从起点开始，逐层向外扩展
- 遇到终点立即返回当前路径长度
3. 代码实现详解
3.1 基础数据结构定义
首先我们需要定义图书馆的地图表示。一个简单的方法是使用二维数组：
python复制# 图书馆地图示例
# 0表示通道，1表示书（障碍物），S表示起点，E表示终点
library = [
['S', 0, 0, 0, 1],
[1, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 'E']
]
3.2 BFS算法实现
下面是完整的BFS实现代码，包含详细注释：
python复制from collections import deque
def find_shortest_path(library):
# 首先找到起点位置
start_pos = None
for i in range(len(library)):
for j in range(len(library[0])):
if library[i][j] == 'S':
start_pos = (i, j)
break
if start_pos:
break
if not start_pos:
return -1 # 没有找到起点
# 定义四个移动方向：上、下、左、右
directions = [(-1,0), (1,0), (0,-1), (0,1)]
# 初始化队列和访问记录
queue = deque()
queue.append((start_pos[0], start_pos[1], 0)) # (行, 列, 步数)
visited = set()
visited.add((start_pos[0], start_pos[1]))
while queue:
row, col, steps = queue.popleft()
# 检查是否到达终点
if library[row][col] == 'E':
return steps
# 尝试四个方向移动
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
# 检查新位置是否有效
if (0 <= new_row < len(library) and
0 <= new_col < len(library[0]) and
library[new_row][new_col] != 1 and # 不是障碍物
(new_row, new_col) not in visited):
visited.add((new_row, new_col))
queue.append((new_row, new_col, steps + 1))
return -1 # 没有找到路径
3.3 代码测试与验证
让我们用之前定义的地图测试这个函数：
python复制print(find_shortest_path(library)) # 输出应为8
这个输出表示老鼠从起点到终点的最短路径需要8步。你可以手动验证这个结果是否正确。
4. 教学要点与常见问题
4.1 教学重点解析
在教授这类题目时，需要特别强调以下几个关键点：
- 地图表示方法：如何用二维数组表示网格地图，以及不同值的含义
- BFS算法原理：队列的使用、访问记录的重要性、逐层扩展的概念
- 边界条件处理：确保不会越界访问数组
- 终止条件：如何判断到达终点
4.2 常见错误与调试技巧
初学者常犯的错误包括：
-
忘记记录已访问位置：这会导致无限循环和重复访问
解决方法：使用集合(Set)明确记录已访问位置
-
方向定义不全：漏掉某些移动方向
检查方向数组是否包含所有可能移动方式
-
边界检查不完整：移动后未检查是否超出地图范围
确保在访问新位置前检查行列索引的有效性
-
起点/终点识别错误：错误识别或未识别起点终点
添加打印语句验证起点终点位置是否正确
4.3 性能优化思考
虽然对于一级考试不需要考虑太复杂的优化，但可以引导学生思考：
- 双向BFS：同时从起点和终点开始搜索，相遇时停止
- 启发式搜索：对于更复杂的地图，可以使用A*算法
- 空间优化：用位图代替集合记录访问位置
5. 题目变体与扩展
5.1 不同难度变体
这个基础题目可以衍生出多种变体，适合不同水平的学生：
- 简单变体：只要求判断是否存在路径，不计算最短距离
- 中等变体：地图中有多个奶酪，需要按特定顺序收集
- 复杂变体：引入传送门、移动障碍物等动态元素
5.2 可视化扩展
为了增加趣味性，可以使用Python的turtle或pygame库将老鼠寻路过程可视化：
python复制import pygame
import time
def visualize_path(library, path):
pygame.init()
cell_size = 50
rows = len(library)
cols = len(library[0]) if rows > 0 else 0
screen = pygame.display.set_mode((cols*cell_size, rows*cell_size))
colors = {
0: (255, 255, 255), # 通道 - 白色
1: (139, 69, 19), # 书 - 棕色
'S': (0, 255, 0), # 起点 - 绿色
'E': (255, 0, 0), # 终点 - 红色
'path': (0, 0, 255) # 路径 - 蓝色
}
# 绘制初始地图
for i in range(rows):
for j in range(cols):
pygame.draw.rect(screen, colors[library[i][j]],
(j*cell_size, i*cell_size, cell_size, cell_size))
pygame.draw.rect(screen, (0,0,0),
(j*cell_size, i*cell_size, cell_size, cell_size), 1)
pygame.display.flip()
# 逐步显示路径
for step in path:
i, j = step
pygame.draw.rect(screen, colors['path'],
(j*cell_size, i*cell_size, cell_size, cell_size))
pygame.draw.rect(screen, (0,0,0),
(j*cell_size, i*cell_size, cell_size, cell_size), 1)
pygame.display.flip()
time.sleep(0.5)
pygame.time.wait(3000)
pygame.quit()
5.3 实际应用延伸
这类网格路径搜索算法在实际中有广泛应用：
- 机器人导航与路径规划
- 游戏AI中的敌人移动
- 物流仓储中的货物分拣路径优化
- 交通网络的最短路线计算
通过这个看似简单的"图书馆老鼠"问题，学生可以掌握计算机科学中许多核心概念的雏形，为后续学习更复杂的算法打下坚实基础。