递归算法求解迷宫触发IndexError的问题排查求助

我尝试用递归算法求解迷宫，但当迷宫存在空路径时总会触发IndexError。我推测是移动未在边界处停止，导致索引越界。以下是部分求解代码及报错信息，希望得到解决思路：

def find_exits(self, start_row, start_col):#depth) -> bool:
    """Find and save all exits into `self._exits` using recursion, save
    the maximum recursion depth into 'self._max_recursion_depth' and mark the maze.

    An exit is an accessible from S empty cell on the outer rims of the maze.

    Args:
        start_row (int): row to start from. 0 represents the topmost cell.
        start_col (int): column to start from; 0 represents the leftmost cell.
        depth (int): Depth of current iteration.

    Raises:
        ValueError: If the starting position is out of range or not walkable path.
    """


    # base case
    if start_row < 0 or start_row >= self._row_range or start_col < 0 or start_col >= self._col_range :
       raise ValueError("Starting position is out of range ")

    if   self._maze[start_row][start_col] == OBSTACLE:
       raise ValueError("Starting position is not a valid path.")
    else:
        self._maze[start_row][start_col] = START


    if self._maze[start_row][start_col] == EXIT and self._maze[start_row][start_col] != OBSTACLE :
            self._exits.append((start_row, start_col))
            return True

    self._maze[start_row][start_col] = VISITED
    for r, c in [
       (0, 1) ,#East
       (1, 1) , #SOUTHEAST
       (1, 0) ,#SOUTH
       (1,-1),#southwest
       (0,-1),#west
       (-1,-1),#northwest
       (-1,0) ,#north
       (-1,1) ,#northeast
    ]:
            # set new position to neighbor
            new_row, new_col = start_row + r, start_col  + c

         
            if  self._maze[new_row][new_col] == PATH:
                self._maze[new_row][new_col] = VISITED
                self.find_exits(new_row, new_col)

报错信息：

[Previous line repeated 27 more times]
  File "C:\Users\alime\OneDrive\Desktop\JKU\A and Ds Ass\ass 3\my_maze.py", line 83, in find_exits
    self._maze[new_row][new_col] == PATH:
    ~~~~~~~~~~~~~~~~~~~^^^^^^^^^
IndexError: list index out of range

问题根源 #

直接访问self._maze[new_row][new_col]前未检查new_row和new_col是否在迷宫合法索引范围内——当递归到迷宫边缘单元格时，向外移动会导致索引超出0 <= row < _row_range、0 <= col < _col_range的范围，触发越界错误。

此外还有几个逻辑漏洞：

• 初始判断中直接将起点设为START，若起点本身是出口（边缘可通行单元格），后续出口判断会被跳过。
• 出口判断条件冗余：== EXIT已隐含不是障碍物，无需额外判断!= OBSTACLE。
• 无回溯逻辑，且单元格状态修改时机错误，可能导致重复访问或路径记录异常。

修复步骤 #

1. 新增边界检查：访问邻居单元格前，先判断索引是否合法，或者在递归函数开头就判断当前位置是否越界，越界则直接返回：

   # 在递归函数开头添加
   if start_row < 0 or start_row >= self._row_range or start_col < 0 or start_col >= self._col_range:
       return
   

   或者在遍历邻居时先检查：

   new_row, new_col = start_row + r, start_col + c
   if 0 <= new_row < self._row_range and 0 <= new_col < self._col_range:
       if self._maze[new_row][new_col] == PATH:
           # 后续递归操作
   

2. 修正出口判断逻辑：出口定义为迷宫边缘的可通行单元格，应先判断当前位置是否在边缘，再确认是否可通行：

   # 检查当前位置是否为出口
   if (start_row == 0 or start_row == self._row_range - 1 or 
       start_col == 0 or start_col == self._col_range - 1):
       if self._maze[start_row][start_col] != OBSTACLE:
           self._exits.append((start_row, start_col))
   

   不要一开始就修改起点状态，应先完成出口判断再标记为已访问。

3. 完善递归逻辑：确保每个单元格只被访问一次，标记为VISITED后再递归探索邻居；若需要保留原始迷宫，可在递归返回后将状态改回PATH（回溯）。

修复后的核心代码示例 #

def find_exits(self, start_row, start_col):
    # 越界直接返回
    if start_row < 0 or start_row >= self._row_range or start_col < 0 or start_col >= self._col_range:
        return
    
    # 障碍物或已访问，直接返回
    if self._maze[start_row][start_col] in (OBSTACLE, VISITED):
        return
    
    # 判断是否为出口
    if (start_row == 0 or start_row == self._row_range - 1 or 
        start_col == 0 or start_col == self._col_range - 1):
        self._exits.append((start_row, start_col))
    
    # 标记为已访问
    self._maze[start_row][start_col] = VISITED
    
    # 遍历8个方向
    directions = [(0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1)]
    for r, c in directions:
        self.find_exits(start_row + r, start_col + c)

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