0

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

该方法完全行不通。任何建议，将不胜感激。

参数：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;
            }
        }
    }



}
4

2 回答 2

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* 算法。很受欢迎。

玩得开心！

于 2014-09-04T13:12:07.037 回答
0

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

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

于 2012-12-08T14:21:15.213 回答