简单递归算法机制

一旦被实例化和方法横动（0,0）被调用时，它会自动解决示出7作为路径和3为“试图路径”迷宫。我试图理解这个代码，但我会卡在遍历方法第一else语句。简单递归算法机制

public class Maze 
{ 
    private final int TRIED = 3; 
    private final int PATH = 7; 
    private int[][] grid = { {1,1,1,0,1,1,0,0,0,1,1,1,1}, 
          {1,0,1,1,1,0,1,1,1,1,0,0,1}, 
          {0,0,0,0,1,0,1,0,1,0,1,0,0}, 
          {1,1,1,0,1,1,1,0,1,0,1,1,1}, 
          {1,0,1,0,0,0,0,1,1,1,0,0,1}, 
          {1,0,1,1,1,1,1,1,0,1,1,1,1}, 
          {1,0,0,0,0,0,0,0,0,0,0,0,0}, 
          {1,1,1,1,1,1,1,1,1,1,1,1,1} }; 

public boolean traverse (int row, int column) 
{ 
    boolean done = false; 
    if (valid (row, column)) 
    { 
     grid[row][column] = TRIED; 
     // this cell has been tried 
     if (row == grid.length-1 && column == grid[0].length-1) 
      done = true; 
      // the maze is solved 
     else 
     { 
      done = traverse (row+1, column); 
      // down 
      if (!done) 
      done = traverse (row, column+1); 
      // right 
      if (!done) 
      done = traverse (row-1, column); 
      // up 

      if (!done) 
      done = traverse (row, column-1); 
      // left 
     } 
    if (done) 
    // this location is part of the final path 
    grid[row][column] = PATH; 
    } 
    return done; 
} 

//----------------------------------------------------------------- 
// Determines if a specific location is valid. 
//----------------------------------------------------------------- 
private boolean valid (int row, int column) 
{ 
    boolean result = false; 
    // check if cell is in the bounds of the matrix 
    if (row >= 0 && row < grid.length && column >= 0 && 
     column < grid[row].length) 
     // check if cell is not blocked and not previously tried 
     if (grid[row][column] == 1) 
     result = true; 
     return result; 
}

据我所知，

done = traverse (row+1, column);

这条线是一个递归调用，并会一次向下移动，并且会再次运行方法，但如果它是不是有效？整个方法不会停止吗？我不明白某个地点无效后控制流程的位置在哪里。

例如，如果[1] [0]是无效的，那么控制转移回[0] [0]调用和处理“走出正确的”说法？在什么地方，如果（完成）意味着什么，我的意思是，当迷宫完全解决并且如果它是有效的，完成等于真，那么整个事情就不会停止？

来源

2012-12-08 Aaron

这是你的方法：

public boolean traverse (int row, int column) 
{ 
    boolean done = false; 
    if (valid (row, column)) 
    { 
     ... 
    } 
    return done; 
}

因此，如果点是无效的，它会跳过所有测试，就回到false。

来源

2012-12-08 03:41:45 Doorknob

返回false后会发生什么？ – Aaron

@Aaron'done'被设置为'false'，它会尝试朝不同的方向前进。 – Doorknob

如果有效测试失败，执行接下来的事情就是“返回完成的;”在方法结束时，将返回false。这会将关于失败的信息传回给调用者。

来源

2012-12-08 03:41:55

在第一别的行和列检查的有效性。如果行和列无效，则该方法不会立即停止，因为根据完成字段的值，第一个else中的嵌套if块将被执行。

来源

2012-12-08 03:43:53

简单递归算法机制

回答

相关问题