C ++递归迷宫求解器无限循环

Question

我是 C++ 的新手，正在尝试编写一个程序来读取文件、动态创建二维数组并使用文件的输入填充数组。然后它使用递归解决迷宫。文本文件如下所示：

前 4 个数字表示行数、列数和起始位置 (X,Y)。 “S”是起点，“O”是路径，“E”是终点。我创建数组或填充数组都没有问题，但是当运行程序调用递归函数解迷宫时遇到错误。这是函数：

bool mazeSolve(char **maze, int startRow, int startCol){
        
  char test = maze[startRow][startCol];
              
  //If maze finds end stop program (Base Case)
  if (test == 'E'){
     cout << "End reached" << endl;
     return true;
  }//End if for base case
       
  //If function can go right
  if (maze[startRow][startCol+1] == 'O'){
     maze[startRow][startCol] = 'P';
     return mazeSolve(maze, startRow, startCol+1);
  }
  
  //If function can go left
  if (maze[startRow][startCol-1] == 'O'){
     maze[startRow][startCol] = 'P';
     return mazeSolve(maze, startRow, startCol-1);
  }
  
  //If function can go up
  if (maze[startRow-1][startCol] == 'O' && startRow-1 >= 0){
     maze[startRow][startCol] = 'P';
     return mazeSolve(maze, startRow-1, startCol);
  }
  
  //If function can go down
  if (maze[startRow+1][startCol] == 'O'){
     maze[startRow][startCol] = 'P';
     return mazeSolve(maze, startRow+1, startCol);
  }
  
  //If function cannot find O's then it will backtrack
  //If function reaches wall, backtrack down
  if (maze[startRow+1][startCol] == 'P'){
        maze[startRow][startCol] = 'C';
        return mazeSolve(maze, startRow+1, startCol);
  }
  
  //If function reaches wall, backtrack up
  if (startRow-1 >= 0 && maze[startRow-1][startCol] == 'P'){
        maze[startRow][startCol] = 'C';
        return mazeSolve(maze, startRow-1, startCol);
  }
  
  //If function reaches wall, backtrack left
  if (maze[startRow][startCol-1] == 'P'){
        maze[startRow][startCol] = 'C';
        return mazeSolve(maze, startRow, startCol-1);
  }
  
  //If function reaches wall, backtrack right
  if (maze[startRow][startCol+1] == 'P'){
        maze[startRow][startCol] = 'C';
        return mazeSolve(maze, startRow, startCol+1);
  }

我已经用谷歌搜索并在这个网站上搜索过类似的问题，但我似乎对递归有一个根本性的误解，因为我无法遵循解决方案。我认为下半部分将允许函数回溯，直到它找到一个新的“O”并最终找到一个“E”，但它正在无限循环。我的教授要求使用 if 语句来完成此操作。我的逻辑哪里错了？任何帮助将不胜感激。

Answer 1

回溯时，首先检查搜索是否成功，如果不成功，则在还原刚才的尝试后尝试不同的选项。

第一个 non-base 案例的实际回溯变体如下所示：

if (maze[startRow][startCol+1] == 'O'){
     auto original = maze[startRow][startCol]; 
     maze[startRow][startCol] = 'P';
     if (mazeSolve(maze, startRow, startCol+1))
         return true;
     maze[startRow][startCol] = original;
}
// ... and keep going with the next attempt ...

Answer 2

经过一番调试，我想通了。从头开始重写函数。谢谢大家的帮助。我添加了越界检查并为 if 语句添加了条件以检查 'O' 和 'E'。奇怪的是回溯 if 语句保持不变，即使我认为它们是问题所在。:

bool mazeSolve(char **maze, int startRow, int startCol){      
            
      //Output test message
      char test = maze[startRow][startCol];
      //cout << test << endl;
                  
      //If maze finds end stop program (Base Case)
      if (test == 'E'){
         cout << "End reached" << endl;
         return true;
      }//End if for base case
      
      //Out of bounds check
      if (startRow < 0 || startCol < 0 || startRow >= arrayRowSize || 
          startCol >= arrayColSize){
          cout << "bounds error";
          return false;   
      }//End out of bounds if
      
      //If function can go down
      if (maze[startRow+1][startCol] == 'O' || maze[startRow+1][startCol] == 'E'){
         maze[startRow][startCol] = 'P';
         //cout << "down" << endl;
         return mazeSolve(maze, startRow+1, startCol);
      } //End down if
      
      //If function can go right
      if (maze[startRow][startCol+1] == 'O' || maze[startRow][startCol+1] == 'E'){
         maze[startRow][startCol] = 'P';
         //cout << "right" << endl;
         return mazeSolve(maze, startRow, startCol+1);
      } //End right if
      
      //If function can go left
      if (maze[startRow][startCol-1] == 'O' || maze[startRow][startCol-1] == 'E'){
         maze[startRow][startCol] = 'P';
         //cout << "left" << endl;
         return mazeSolve(maze, startRow, startCol-1);
      } //End left if
      
      //If function can go up
      if (maze[startRow-1][startCol] == 'O' || maze[startRow-1][startCol] == 'E'){
         maze[startRow][startCol] = 'P';
         //cout << "right" << endl;
         return mazeSolve(maze, startRow-1, startCol);
      } //End up if     
      
      //If function cannot find O's then it will backtrack
      //If function reaches wall, backtrack down
      if (maze[startRow+1][startCol] == 'P'){
            maze[startRow][startCol] = '*';
            return mazeSolve(maze, startRow+1, startCol);
      } //End backtrack down if
      
      //If function reaches wall, backtrack up
      if (maze[startRow-1][startCol] == 'P'){
            maze[startRow][startCol] = '^';
            return mazeSolve(maze, startRow-1, startCol);
      } //End backtrack up if
      
      //If function reaches wall, backtrack left
      if (maze[startRow][startCol-1] == 'P'){
            maze[startRow][startCol] = '<';
            return mazeSolve(maze, startRow, startCol-1);
      } //End backtrack left if
      
      //If function reaches wall, backtrack right
      if (maze[startRow][startCol+1] == 'P'){
            maze[startRow][startCol] = '>';
            return mazeSolve(maze, startRow, startCol+1);
            //End backtrack right if
      } else 
         return false;//If all else fails, maze is unsolvable            
}

这解决了迷宫。如果迷宫没有尽头，我现在唯一的问题是错误处理。我将 txt 文件编辑为没有“E”，函数无限循环。我认为最后的“else”声明会涵盖这一点，但事实并非如此。遇到无法解开的迷宫应该怎么办？

C ++递归迷宫求解器无限循环

C++ Recursive Maze Solver looping infinitely

c++

class

recursion

solver

maze