色盲视角下的连通块问题：用Python和BFS两种解法复现米哈游暑期实习笔试

色盲视角下的连通块问题Python与BFS双解剖析引言当算法遇见色盲视角在算法面试中网格搜索类问题一直是高频考点。而这道来自米哈游的笔试题巧妙地将连通块问题与色盲视角结合不仅考察基础算法能力更检验开发者对问题本质的理解。题目要求我们计算色盲视角下连通块数量与真实情况的差异这需要同时处理两种不同的颜色判定逻辑。对于准备算法面试的开发者而言这类问题极具代表性。它融合了以下核心技能点二维矩阵的遍历与搜索连通块计数算法DFS/BFS条件判断与状态标记算法效率优化本文将用Python实现两种解法DFS和BFS并深入分析它们的性能差异。我们还会探讨如何针对1000×1000的大矩阵进行优化确保算法在笔试环境下的高效运行。1. 问题分析与建模1.1 理解连通块与色盲视角连通块是指矩阵中相邻上下左右且颜色相同的区域。在本题中存在两种视角真实视角区分R、G、B三种颜色色盲视角将G和B视为同一种颜色我们需要分别计算两种视角下的连通块数量然后求其差值。1.2 输入输出示例解析以题目给出的示例为例2 6 RRGGBB RGBGRR真实连通块第一行RR、GG、BB → 3块第二行R、G、B、G、RR → 5块 但实际连通块是整体矩阵中相连的区域所以真实连通块为6个。色盲视角连通块 将G视为B后第一行RR、BBBB → 2块第二行R、BB、B、RR → 3块 实际连通块为3个。因此输出结果为6-33。1.3 算法选择考量对于网格搜索问题通常有DFS和BFS两种基本方法方法优点缺点适用场景DFS代码简洁递归实现方便栈溢出风险Python递归深度约1000小规模矩阵BFS迭代实现无栈溢出问题需要队列数据结构大规模矩阵考虑到题目中矩阵可能达到1000×1000我们将优先实现BFS解法同时也会展示DFS实现作为对比。2. BFS解法实现2.1 基础BFS框架BFS广度优先搜索使用队列来逐层遍历相邻节点。以下是基础框架from collections import deque def bfs(matrix, visited, i, j, target_color): queue deque() queue.append((i, j)) visited[i][j] True directions [(-1,0),(1,0),(0,-1),(0,1)] # 上下左右 while queue: x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx len(matrix) and 0 ny len(matrix[0]): if not visited[nx][ny] and matrix[nx][ny] target_color: visited[nx][ny] True queue.append((nx, ny))2.2 完整BFS解法代码from collections import deque def count_blocks(matrix, is_color_blindFalse): n len(matrix) m len(matrix[0]) if n 0 else 0 visited [[False for _ in range(m)] for _ in range(n)] count 0 for i in range(n): for j in range(m): if not visited[i][j]: # 获取当前颜色考虑色盲视角 current_color matrix[i][j] if is_color_blind and current_color G: current_color B # BFS遍历连通区域 queue deque([(i, j)]) visited[i][j] True while queue: x, y queue.popleft() 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: cell_color matrix[nx][ny] if is_color_blind and cell_color G: cell_color B if not visited[nx][ny] and cell_color current_color: visited[nx][ny] True queue.append((nx, ny)) count 1 return count def solve(): n, m map(int, input().split()) matrix [input().strip() for _ in range(n)] real_count count_blocks(matrix, is_color_blindFalse) color_blind_count count_blocks(matrix, is_color_blindTrue) print(real_count - color_blind_count) if __name__ __main__: solve()2.3 性能优化技巧对于1000×1000的大矩阵需要注意以下优化点避免频繁内存分配预分配visited数组而不是每次count_blocks调用时新建使用一维数组代替二维数组可以提升缓存命中率队列实现选择collections.deque比list的pop(0)效率更高对于极大规模数据可以考虑使用queue.Queue提前终止条件如果所有单元格都已访问可以提前结束循环优化后的visited初始化visited [[False]*m for _ in range(n)] # 比列表推导式稍快3. DFS解法实现3.1 递归DFS实现虽然Python的递归深度有限但对于理解问题很有帮助def dfs(matrix, visited, i, j, target_color, is_color_blind): if i 0 or i len(matrix) or j 0 or j len(matrix[0]): return if visited[i][j]: return cell_color matrix[i][j] if is_color_blind and cell_color G: cell_color B if cell_color target_color: visited[i][j] True dfs(matrix, visited, i1, j, target_color, is_color_blind) dfs(matrix, visited, i-1, j, target_color, is_color_blind) dfs(matrix, visited, i, j1, target_color, is_color_blind) dfs(matrix, visited, i, j-1, target_color, is_color_blind)3.2 迭代DFS实现为避免递归深度问题可以用栈实现迭代DFSdef dfs_iterative(matrix, visited, i, j, is_color_blind): stack [(i, j)] target_color matrix[i][j] if is_color_blind and target_color G: target_color B while stack: x, y stack.pop() if visited[x][y]: continue visited[x][y] True for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]: nx, ny x dx, y dy if 0 nx len(matrix) and 0 ny len(matrix[0]): cell_color matrix[nx][ny] if is_color_blind and cell_color G: cell_color B if not visited[nx][ny] and cell_color target_color: stack.append((nx, ny))3.3 DFS与BFS性能对比在笔试环境中对于1000×1000的矩阵方法时间空间适用性递归DFS栈溢出O(nm)不推荐迭代DFSO(nm)O(nm)可用BFSO(nm)O(nm)推荐提示Python中递归深度默认约1000对于1000×1000矩阵的递归DFS很可能会栈溢出。建议使用BFS或迭代DFS。4. 测试用例与边界条件4.1 标准测试用例test_cases [ ([RRGGBB, RGBGRR], 3), # 题目示例 ([RRRR, RRRR], 0), # 全同色 ([RGB, GBR], 2), # 3x2矩阵 ([R], 0), # 单元素 ([RG, GB], 1) # 2x2矩阵 ]4.2 极端情况测试最大规模测试1000×1000全R矩阵 → 应返回0交替RG的1000×1000矩阵 → 真实块数500000色盲块数500特殊模式测试棋盘式分布R和G交替螺旋式颜色分布4.3 自动化测试框架def run_tests(): for matrix, expected in test_cases: real count_blocks(matrix, False) blind count_blocks(matrix, True) result real - blind assert result expected, fFailed: {matrix}, got {result}, expected {expected} print(All tests passed!) run_tests()5. 扩展思考与实际应用5.1 算法变种与相似题目岛屿问题变种不同颜色代表不同海拔高度考虑对角线连通八连通实际应用场景图像处理中的区域分割游戏开发中的地图区域划分社交网络中的群体检测5.2 性能优化进阶对于特别大的矩阵如10000×10000可以考虑并行计算将矩阵分块处理使用多进程计算不同区域内存优化使用位图表示visited数组分块处理减少内存占用Union-Find算法适用于动态连通性问题可以边读取数据边计算5.3 面试技巧与注意事项编码前确认要点明确连通定义四连通/八连通确认颜色处理规则询问矩阵规模以选择合适算法代码风格建议提取颜色判断逻辑为独立函数使用有意义的变量名添加必要注释调试技巧先在小矩阵上验证打印中间结果检查编写可视化输出函数def visualize(matrix, visited): for i in range(len(matrix)): row [] for j in range(len(matrix[0])): row.append(X if visited[i][j] else matrix[i][j]) print(.join(row))