Python基于广度优先搜索实现迷宫功能时出现无限循环问题

代码现存的核心缺陷 #

• 起点定位逻辑完全失效
  所有查找起点S的循环都存在逻辑错误：遍历range(len(maze[0]))得到的是整数索引，直接拿整数和字符串'S'做等值匹配永远不会命中，starting_point始终保持初始值0。部分代码里还引用了未定义的行变量i，运行时会直接触发变量未定义报错。
• 已访问标记逻辑完全失效
  find_solution函数每次被调用时都会把visited列表重置为空，后续向visited追加的也不是已到达的坐标值，而是单个移动指令的字符串，等于永远记不住哪些位置已经遍历过，同一个位置会通过不同指令组合被反复加入队列，最终触发无限循环。
  而且当前BFS存储的是整段移动指令字符串，没有和具体坐标做绑定，根本没法基于坐标去重。
• 移动指令解析逻辑错误
  finished_maze函数里直接遍历solution字符串的单个字符，没有用正则拆分完整的指令词，拿到的是单个字母，永远匹配不到'Up'/'Down'这类完整指令，路径移动计算完全错误。
• 边界判断逻辑错误
  is_valid函数里判断行号k的合法范围时，错把列数len(maze[0])作为上界，行号的合法范围应该是0 <= k < len(maze)，行总数和列数的差异会导致频繁数组越界。
• 坐标赋值逻辑混乱
  代码里定义j为列坐标、k为行坐标，但查找起点时错误把整行字符串maze[position]赋值给starting_point，类型和值完全不匹配，后续坐标计算全部错位。
• 路径回溯能力缺失
  原设计预期遍历完成后回溯生成最短路径，但当前BFS只存储移动指令序列，没有记录每个坐标的前驱节点，既没法高效回溯路径，也无法把路径上的位置标记为1。

正确实现的核心思路 #

• 先全量遍历迷宫，逐行逐列匹配字符：找到值为'S'的起点坐标、值为'E'的终点坐标，用(row, col)元组存储。
• BFS队列的入队元素统一存储(当前坐标, 到达当前坐标的路径)，已访问集合直接存储所有已经入过队的坐标元组，只要坐标在集合内就不再重复入队，从根源上避免重复遍历。
• 通行性判断同时满足三个条件：坐标在行、列的合法边界内，当前位置不是墙值'0'，且坐标没有被访问过。
• 当BFS出队的坐标是终点坐标时，直接终止遍历，收集路径上的所有坐标，打印迷宫时将这些位置替换为标记值1，其余位置保持原迷宫字符。

内容的提问来源于stack exchange，提问作者James