应该检查 8 个方向的迷宫求解器方法，检查甚至不存在的方向

Question

public boolean findSolution() {
 boolean finish = false; //finish should become true when a solution is found or it is determined that there is no solution
 boolean success = false;  //success should become true when a solution is found

 //The following can be used to compute each of 8 directions
 //one can move from their current position (row,column).
 int[][] offset ={
                 {1,0},   //Down
                 {1,-1},  //DownLeft
                 {0,-1},  //Left
                 {-1,-1}, //UpLeft
                 {-1,0},  //Up
                 {-1,1},  //UpRight
                 {0,1},   //Right
                 {1,1}    //DownRight
             };


 //Push information onto the stack indicating the first choice
 //is the position of row 0 and column 9. The last value is face, put -1 as     default
 Position nextPosition = new Position(0, 9, -1);
 stackSoln.push(nextPosition);

 while (finish == false && stackSoln.isEmpty( ) == false) {
 //check the last position
 int currentRow = stackSoln.peek().getRow();
 int currentCol = stackSoln.peek().getColumn();

 System.out.println("Trying the position of row "
                    + currentRow
                    + " and column "
                    + currentCol);
 int newRow = -1;
 int newColumn=-1;

for (int k = 0; k < 8; k++)
 {
    newRow =  currentRow + offset[k][0];
    newColumn = currentCol + offset[k][1];


    //get a new position and push it
     nextPosition = new Position(newRow, newColumn, -1);
     stackSoln.push(nextPosition);

    if (newRow < 9 && newColumn < 9 && newRow > 0 &&
     newColumn > 0  && (maze[newRow][newColumn] == 'x' &&
     maze[newRow][newColumn] == '.' || 
     maze[newRow][newColumn] == '<' || maze[newRow][newColumn] == 
    '>'))

    {
         if (maze[newRow][newColumn] == '<') //end of the maze
         {
             nextPosition.setFace(k);
             success = true;
             finish = true;
         }
         else if (maze[newRow][newColumn] == '.') //able to move  
         {
             maze[newRow][newColumn] = 'x';
             nextPosition.setFace(k);
             break;
         }
         else 
         {
             maze[newRow][newColumn] = 'O'; //unable to move, therefore pop the position.
             stackSoln.pop();
         }

         if (stackSoln.isEmpty() == true)
         {
             success = false;
             finish = true; 
         }

    }

 }

  } //end of while loop

  return success;

}//end of findSolution method

给出这样的输入：http://i.imgur.com/16KTaox.png

应该是return:

Trying the position of row 0 and column 9
Trying the position of row 1 and column 8
Trying the position of row 2 and column 7
Trying the position of row 3 and column 7
Trying the position of row 4 and column 7
Trying the position of row 4 and column 6
Trying the position of row 5 and column 5
Trying the position of row 4 and column 4
Trying the position of row 5 and column 3
Trying the position of row 6 and column 3
Trying the position of row 7 and column 3
Trying the position of row 8 and column 3
Trying the position of row 9 and column 2
Trying the position of row 9 and column 1

但是，我的代码会执行如下操作：

 Trying the position of row 59834 and column 59843
 Trying the position of row 59835 and column 59844
 Trying the position of row 59836 and column 59845...etc

出于某种原因，如果我将 for 循环中的主要 if 语句更改为 ors 而不是 ands，它会得到正确的值直到最后一个值，然后它会得到一个索引越界错误。我不知道为什么，因为在这种情况下不应该使用 ors...

Answer 1

问题是您在检查行和列是否有效之前将新位置压入堆栈。

查看代码中的这些行：

//get a new position and push it
 nextPosition = new Position(newRow, newColumn, -1);
 stackSoln.push(nextPosition);

与其立即将 nextPosition 压入堆栈，不如等到您验证了该位置。

您可能希望将位置推入此 if 语句保护的块内的堆栈：

if (newRow <= 9 && newColumn <= 9 && newRow > 0 &&
         newColumn > 0  && (maze[newRow][newColumn] == 'x' &&
       maze[newRow][newColumn] == '.' ||
       maze[newRow][newColumn] == '<' || maze[newRow][newColumn] ==
      '>'))

但是，条件表达式存在一些问题。您应该接受 newRow 和 newColumn 的零值。此外，您在迷宫中检查字符的部分很复杂且不正确，因为您将 && 与 || 混合在一起，并且因为您没有考虑到 O 字符重新投入迷宫。

我建议你改用这个表达式：

if (newRow >= 0 && newRow < mazeSize &&
    newColumn >= 0 && newColumn < mazeSize &&
    maze[newRow][newColumn] != '#')

请注意，最好使用 class 属性 mazeSize 而不是硬编码值。这允许表达式适用于不同的迷宫大小。

您的代码中还有其他问题不属于此问题的范围。

应该检查 8 个方向的迷宫求解器方法，检查甚至不存在的方向

Maze solver method that is supposed to check 8 directions, checks directions that aren't even there

java

arrays

algorithm

double

maze