最近在刷算法题时遇到了一个很有意思的题目——镜中世界这是一道典型的图论与动态规划结合的问题。我在周赛中拿到了232分的成绩虽然不算顶尖但解题过程中积累了不少实战经验。本文将完整分享这道题的解题思路、代码实现以及优化技巧无论是算法新手还是有一定基础的开发者都能从中获得启发。1. 题目理解与问题分析1.1 题目背景描述镜中世界是一个虚构的迷宫探索问题。题目描述了一个由镜子构成的特殊迷宫玩家需要从起点到达终点但迷宫中存在特殊的反射规则当光线或玩家遇到镜子时会根据镜子的朝向改变行进方向。1.2 核心问题拆解这道题的本质是一个带有状态转移的图搜索问题需要同时考虑位置坐标和行进方向两个维度。具体来说我们需要解决以下几个关键点状态表示每个状态需要记录当前位置(x,y)和当前行进方向状态转移根据当前位置的镜子类型决定下一个状态路径搜索找到从起点到终点的最短路径边界处理处理越界情况和特殊边界条件1.3 输入输出格式典型的输入格式如下迷宫大小n x m 的网格镜子布局每个格子可能是空位(.)、左斜镜(/)、右斜镜(\)起点和终点坐标输出要求最短路径步数如果无法到达则返回-12. 算法思路设计2.1 基础思路选择面对这类问题我们首先考虑使用广度优先搜索(BFS)因为BFS天然适合求解最短路径问题。但普通的BFS只能处理位置信息而本题还需要考虑方向状态。2.2 状态空间建模我们需要将传统的二维BFS扩展为三维BFS第三个维度就是方向。具体来说状态定义为(x, y, direction)方向通常用数字表示0-上1-右2-下3-左使用三维visited数组记录访问状态2.3 镜子反射规则这是本题的核心难点需要精确处理不同镜子类型下的方向变化左斜镜(/)的反射规则从上方来 → 反射向右从右方来 → 反射向上从下方来 → 反射向左从左方来 → 反射向下右斜镜(\)的反射规则从上方来 → 反射向左从左方来 → 反射向上从下方来 → 反射向右从右方来 → 反射向下2.4 算法框架设计基于以上分析我们设计以下算法框架初始化BFS队列包含起点位置和初始方向使用三维数组记录访问状态逐层扩展直到找到终点或队列为空对于每个状态根据镜子类型计算下一个状态记录步数返回最短路径3. 代码实现详解3.1 基础数据结构定义首先定义必要的常量和数据结构from collections import deque # 方向常量上、右、下、左 DIRECTIONS [(-1, 0), (0, 1), (1, 0), (0, -1)] def mirror_world_bfs(grid, start, end): 解决镜中世界问题的BFS算法 :param grid: 二维网格包含镜子信息 :param start: 起点坐标 (x, y) :param end: 终点坐标 (x, y) :return: 最短路径步数无法到达返回-1 n, m len(grid), len(grid[0]) # 三维访问数组visited[x][y][direction] visited [[[False] * 4 for _ in range(m)] for _ in range(n)] # BFS队列(x, y, direction, steps) queue deque()3.2 方向处理函数实现镜子反射的方向转换逻辑def get_next_direction(current_dir, mirror_type): 根据当前方向和镜子类型计算下一个方向 :param current_dir: 当前方向(0-3) :param mirror_type: 镜子类型(., /, \\) :return: 下一个方向列表 if mirror_type .: # 空位方向不变 return [current_dir] elif mirror_type /: # 左斜镜 # 反射规则映射 reflection_map {0: 1, 1: 0, 2: 3, 3: 2} return [reflection_map[current_dir]] elif mirror_type \\: # 右斜镜 # 反射规则映射 reflection_map {0: 3, 3: 0, 2: 1, 1: 2} return [reflection_map[current_dir]] else: # 其他情况如起点终点 return [current_dir]3.3 BFS核心逻辑实现完整的BFS搜索算法def mirror_world_bfs(grid, start, end): n, m len(grid), len(grid[0]) visited [[[False] * 4 for _ in range(m)] for _ in range(n)] queue deque() # 从起点向四个方向同时开始搜索 start_x, start_y start end_x, end_y end for direction in range(4): queue.append((start_x, start_y, direction, 0)) visited[start_x][start_y][direction] True while queue: x, y, direction, steps queue.popleft() # 到达终点 if (x, y) (end_x, end_y): return steps # 获取当前格子的镜子类型 mirror_type grid[x][y] # 计算下一个方向 next_directions get_next_direction(direction, mirror_type) for next_dir in next_directions: dx, dy DIRECTIONS[next_dir] nx, ny x dx, y dy # 检查边界 if 0 nx n and 0 ny m: if not visited[nx][ny][next_dir]: visited[nx][ny][next_dir] True queue.append((nx, ny, next_dir, steps 1)) return -1 # 无法到达终点3.4 完整可运行示例提供一个完整的测试用例def test_mirror_world(): # 测试用例1简单直线路径 grid1 [ [., ., .], [., ., .], [., ., .] ] start1 (0, 0) end1 (2, 2) result1 mirror_world_bfs(grid1, start1, end1) print(f测试1结果: {result1}) # 应该输出4 # 测试用例2有镜子的复杂路径 grid2 [ [., /, .], [., ., \\], [., ., .] ] start2 (0, 0) end2 (2, 2) result2 mirror_world_bfs(grid2, start2, end2) print(f测试2结果: {result2}) if __name__ __main__: test_mirror_world()4. 性能优化技巧4.1 双向BFS优化对于大规模网格可以使用双向BFS来加速搜索def bidirectional_bfs(grid, start, end): n, m len(grid), len(grid[0]) # 前向和后向的访问数组 forward_visited [[[False] * 4 for _ in range(m)] for _ in range(n)] backward_visited [[[False] * 4 for _ in range(m)] for _ in range(n)] forward_queue deque() backward_queue deque() # 初始化队列 start_x, start_y start end_x, end_y end for direction in range(4): forward_queue.append((start_x, start_y, direction, 0)) forward_visited[start_x][start_y][direction] True backward_queue.append((end_x, end_y, direction, 0)) backward_visited[end_x][end_y][direction] True while forward_queue and backward_queue: # 交替扩展前向和后向搜索 if len(forward_queue) len(backward_queue): result expand_level(forward_queue, forward_visited, backward_visited, grid, True) else: result expand_level(backward_queue, backward_visited, forward_visited, grid, False) if result ! -1: return result return -14.2 状态压缩技巧对于内存敏感的场景可以使用位运算压缩状态def compress_state(x, y, direction, m): 将状态压缩为一个整数 return (x * m y) * 4 direction def decompress_state(state, m): 从压缩状态解包 direction state % 4 pos state // 4 y pos % m x pos // m return x, y, direction4.3 提前终止优化添加合理性检查提前终止不可能的情况def is_reachable(grid, start, end): 检查起点终点是否可达的快速验证 n, m len(grid), len(grid[0]) # 简单的连通性检查 visited [[False] * m for _ in range(n)] queue deque([start]) visited[start[0]][start[1]] True while queue: x, y queue.popleft() if (x, y) end: return True for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]: nx, ny x dx, y dy if 0 nx n and 0 ny m and not visited[nx][ny]: visited[nx][ny] True queue.append((nx, ny)) return False5. 常见错误与调试技巧5.1 方向映射错误这是最容易出错的地方务必仔细验证方向映射关系def test_direction_mapping(): 测试方向映射的正确性 test_cases [ (0, /, 1), # 上→右 (1, /, 0), # 右→上 (2, /, 3), # 下→左 (3, /, 2), # 左→下 (0, \\, 3), # 上→左 (3, \\, 0), # 左→上 (2, \\, 1), # 下→右 (1, \\, 2) # 右→下 ] for current_dir, mirror_type, expected in test_cases: result get_next_direction(current_dir, mirror_type)[0] assert result expected, f方向映射错误: {current_dir},{mirror_type}-{result}, 期望:{expected}5.2 边界条件处理特别注意网格边界的处理def safe_move(x, y, direction, n, m): 安全的移动函数处理边界情况 dx, dy DIRECTIONS[direction] nx, ny x dx, y dy if 0 nx n and 0 ny m: return nx, ny else: return None # 越界5.3 内存使用优化对于大规模网格注意内存使用def memory_efficient_bfs(grid, start, end): 内存优化的BFS版本 n, m len(grid), len(grid[0]) # 使用集合而不是三维数组节省内存 visited set() queue deque() start_x, start_y start for direction in range(4): state (start_x, start_y, direction) visited.add(state) queue.append((state, 0)) while queue: (x, y, direction), steps queue.popleft() if (x, y) end: return steps mirror_type grid[x][y] next_dirs get_next_direction(direction, mirror_type) for next_dir in next_dirs: next_pos safe_move(x, y, next_dir, n, m) if next_pos: nx, ny next_pos next_state (nx, ny, next_dir) if next_state not in visited: visited.add(next_state) queue.append((next_state, steps 1)) return -16. 算法复杂度分析6.1 时间复杂度最坏情况O(n × m × 4) O(4nm)每个格子最多被4个方向各访问一次在实际比赛中通常能够通过所有测试用例6.2 空间复杂度主要开销visited数组O(n × m × 4)队列空间O(n × m × 4) 最坏情况对于1000×1000的网格需要约4MB内存假设boolean为1字节6.3 实际性能测试提供性能测试代码import time import random def performance_test(): 性能测试函数 n, m 100, 100 grid [[. for _ in range(m)] for _ in range(n)] # 随机添加一些镜子 for i in range(n): for j in range(m): if random.random() 0.2: # 20%的格子有镜子 grid[i][j] / if random.random() 0.5 else \\ start (0, 0) end (n-1, m-1) start_time time.time() result mirror_world_bfs(grid, start, end) end_time time.time() print(f网格大小: {n}x{m}) print(f结果: {result}) print(f耗时: {end_time - start_time:.4f}秒)7. 变种问题与扩展思考7.1 多镜子类型扩展可以扩展支持更多镜子类型def extended_mirror_rules(current_dir, mirror_type): 扩展的镜子规则 if mirror_type |: # 垂直镜 if current_dir in [0, 2]: # 上下方向通过 return [current_dir] else: # 左右方向反射 return [0, 2] # 分为上下两个方向 elif mirror_type -: # 水平镜 if current_dir in [1, 3]: # 左右方向通过 return [current_dir] else: # 上下方向反射 return [1, 3] # 分为左右两个方向 else: return get_next_direction(current_dir, mirror_type)7.2 带权图版本如果不同路径有不同代价可以改用Dijkstra算法import heapq def dijkstra_mirror_world(grid, start, end): 带权重的镜子世界问题 n, m len(grid), len(grid[0]) dist [[[float(inf)] * 4 for _ in range(m)] for _ in range(n)] heap [] start_x, start_y start for direction in range(4): dist[start_x][start_y][direction] 0 heapq.heappush(heap, (0, start_x, start_y, direction)) while heap: cost, x, y, direction heapq.heappop(heap) if (x, y) end: return cost if cost dist[x][y][direction]: continue mirror_type grid[x][y] next_dirs get_next_direction(direction, mirror_type) for next_dir in next_dirs: next_pos safe_move(x, y, next_dir, n, m) if next_pos: nx, ny next_pos # 假设每一步代价为1可以根据实际情况调整 new_cost cost 1 if new_cost dist[nx][ny][next_dir]: dist[nx][ny][next_dir] new_cost heapq.heappush(heap, (new_cost, nx, ny, next_dir)) return -17.3 实时查询优化对于需要多次查询的场景可以预处理整个网格class MirrorWorldSolver: 预处理的镜子世界求解器 def __init__(self, grid): self.grid grid self.n len(grid) self.m len(grid[0]) self.preprocessed self._preprocess() def _preprocess(self): 预处理所有格子到所有方向的最短路径 # 实现预处理逻辑 pass def query(self, start, end): 快速查询最短路径 # 使用预处理结果快速计算 pass通过本文的详细讲解相信大家对镜中世界这类问题有了深入的理解。关键是要掌握状态扩展的思想将传统BFS从二维扩展到三维加入方向维度。在实际编程比赛中这类问题考察的就是对基础算法的灵活运用和细节处理能力。