递归迷宫求解方法.

Question

我正在研究一种递归求解由单元格组成的方法。

这种方法根本不起作用。任何建议将不胜感激。

参数：srow = 起始 x 值。 scol = 凝视 y 值 erow = 结束 x 值。ecol = 结束 y 值。L = 已解决路径点的链表

法典：

private InputGraphicMaze2 maze;
private int R, C; 
//code added by me
private String[] [] cell; //an array to keep track of cells that are proven dead ends. 

public YourMazeWithPath2() 
{       
   // an R rows x C columns maze
  maze = new InputGraphicMaze2();
  R=maze.Rows(); C=maze.Cols();  
  //code added by me
  cell = new String[R+2][C+2];
  for (int i=0; i<R+2; i++) {
      for (int k=0; k<C+2; k++) {
          cell[i][k] = "no";
      }
  }
  // Path holds the cells of the path
  LinkedList<Point> Path = new LinkedList<Point>();
   // Create the path
   CreatePath(maze, 1, 1, R, C, Path);
   // show the path in the maze
   maze.showPath(Path);
}
private void setDead(int x, int y) {
    cell[x][y] = "dead";
}
private void setVisited(int x, int y) {
    cell[x][y] = "visited";
}
public boolean CreatePath(InputGraphicMaze2 maze,      
  int srow, int scol, int erow, int ecol, LinkedList<Point> L)
{
    int x = srow;
    int y = scol;
    Point p = new Point(x, y);
    if ((x<1) || (y<1) || (x>R) || (y>C)) {
        return false; //cell is out of bounds
    }
    else if ((x==R) && (y==C)) {
        return true; // cell is the exit cell
    }
    else {
        if ((maze.can_go(x, y, 'U')) && (x!=1) && (!cell[x-1][y].equals("dead")) && (!cell[x-1][y].equals("visited"))) {
            L.addLast(p);
            setVisited(x,y);
            CreatePath(maze, x-1, y, R, C, L);
            return false;
        }
        else if ((maze.can_go(x, y, 'R')) && (y!=C) && (!cell[x][y+1].equals("dead")) && (!cell[x][y+1].equals("visited"))) {
            L.addLast(p);
            setVisited(x, y);
            CreatePath(maze, x, y+1, R, C, L);
            return false;
        }
        else if ((maze.can_go(x, y, 'D')) && (x!=R) && (!cell[x+1][y].equals("dead")) && (!cell[x+1][y].equals("visited"))) {
            L.addLast(p);
            setVisited(x, y);
            CreatePath(maze, x+1, y, R, C, L);
            return false;
        }
        else if ((maze.can_go(x, y, 'L')) && (y!=1) && (!cell[x][y-1].equals("dead")) && (!cell[x][y-1].equals("visited"))) {
            L.addLast(p);
            setVisited(x, y);
            CreatePath(maze, x, y-1, R, C, L);
            return false;
        }
        else {
            if ((maze.can_go(x, y, 'U')) && (x!=1) && (cell[x][y-1].equals("visited"))) {
                setDead(x, y);
                if (L.contains(p))
                    L.remove(p);
                CreatePath(maze, x-1, y, R, C, L);
                return false;
            }
            else if ((maze.can_go(x, y, 'R')) && (y!=C) && (cell[x][y+1].equals("visited"))) {
                setDead(x, y);
                if (L.contains(p))
                    L.remove(p);
                CreatePath(maze, x, y+1, R, C, L);
                return false;
            }
            else if ((maze.can_go(x, y, 'D')) && (x!=R) && (cell[x+1][y].equals("visited"))) {
                setDead(x, y);
                if (L.contains(p))
                    L.remove(p);
                CreatePath(maze, x+1, y, R, C, L);
                return false;
            }
            else if ((maze.can_go(x, y, 'D')) && (y!=1) && (cell[x][y-1].equals("visited"))) {
                setDead(x, y);
                if (L.contains(p))
                    L.remove(p);
                CreatePath(maze, x, y-1, R, C, L);
                return false;
            }
            else {
                return false;
            }
        }
    }

}

Answer 1

来自另一个类似的线程，只是为了用不那么冗长的语言看到问题，看看这个由用户@Sergey Rudenko制作的小型JS递归迷宫求解器

var map = [
    [1,1,0,0,0,0,0,0],
    [0,1,1,0,0,0,0,0],
    [1,1,1,0,0,0,0,0],
    [1,0,0,1,1,1,1,1],
    [1,1,0,0,1,0,0,1],
    [0,1,1,0,1,0,0,1],
    [1,1,1,0,1,0,0,1],
    [1,0,0,0,1,1,1,1]
]
var goalx = 7;
var goaly = 7;
function findpath(x,y){
    // illegal move check
    if (x < 0 || x > (map[0].length -1) || y < 0 || y > (map.length - 1)) return false; //if it is outside of map
    if (map[y][x]==0) return false; //it is not open
    // end move check
    if (x== goalx && y== goaly){
        console.log('Reached goal at: ' + x + ':' + y);
        return true; // if it is the goal (exit point)
    }
    if(map[y][x] == 9 || map[y][x] == 8)
        return false;
    console.log('Im here at: ' + x + ':' + y);
    map[y][x]=9; //here marking x,y position as part of solution path outlined by "9"
    if(findpath(x+1,y)) 
        return true;    
    if(findpath(x,y+1)) 
        return true;    
    if(findpath(x,y-1))
        return true;
    if(findpath(x-1,y)) 
        return true;                    
    return false;
};
findpath(0, 0);

JSfiddle

是的。它很小，简单，幼稚和缺乏，但哎呀，它的递归和它有效！此外，您可以清楚地看到许多迷宫遍历算法的共同部分。

对于更严肃的阅读，此页面提供了关于许多游戏相关算法的优秀深入但不科学的论文教程。

购买算法时，有一些相关问题需要回答：

需要任何解决方案？

需要所有解决方案？

需要最快的？

迷宫的地形是什么？网格？图表？

想在未来实施移动成本吗？

想要实施启发式方法以选择最佳路由？

最后，如果您还没有遇到它，请检查 a* 算法。很受欢迎。

玩得愉快！

Answer 2

这是一个基本的图遍历问题。我建议你使用dfs而不是bfs。几乎任何关于算法和数据结构的教科书都会有实现。

您只需调整递归部分即可在达到目标后停止搜索。另一方面，如果您正在寻找通往目标的所有路径，只需执行所有路径，然后从那里开始。有关提示，您可以查找Bellman-Ford或Dijkstra的算法（http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm）。同样，任何带有图表章节的好教科书。