求走迷宫问题的算法,要求用非递归回溯的方法写?

求走迷宫问题的算法,要求用非递归回溯的方法写?
迷宫是由许多小方格构成的矩形,在每个小方格中有的是墙(“1”),有的是路(“0”),以下是一个迷宫示例:走迷宫就是从某一个小方格在不能穿墙时,沿上、下、左、右四个方向走到邻近的方格。要求:(1)设迷宫的入口是在左上角,出口是右下角,根据给定的迷宫,找出任意一条从入口到出口的路径;(2)用栈完成非递归算法,作用是保存已走过的来路,如果当前无法找到向前的路径时,回退到栈顶的位置试探新方向;
sdsdcwe 1年前 已收到1个回答 举报

奔树 幼苗

共回答了21个问题采纳率:95.2% 举报

public class MyMaze { private class Point { //自定义数组下标记录类型 int x = 0;
int y = 0; public Point() {
this(0, 0);
} public Point(int x, int y) {
this.x = x;
this.y = y;
} public boolean equals(Point p) {
return (x == p.x) && (y == p.y);
} @Override
public String toString() {
return "(" + x + "," + y + ")";
}
} private int[][] maze = null; //迷宫图
private java.util.Stack stack = new java.util.Stack();
//保存路径的栈 public MyMaze(int[][] maze) {
this.maze = maze;
} public void go() {
Point out = new Point(maze.length-1, maze[0].length-1); //出口
Point in = new Point(0,0); //入口
Point curNode = in; //当前点为入口
Point nextNode = null; //下一个访问点(目标点) while(!curNode.equals(out)) {
nextNode = new Point(curNode.x,curNode.y); //设置目标点为当前点,便于下面偏移
if((curNode.x+1)=0&&maze[curNode.x][curNode.y-1]==0) { //如果左边是空的,则目标点向左偏移
nextNode.y--;
} else { //这里是没有路的状态
maze[curNode.x][curNode.y] = 3; //标记为死路
if(stack.isEmpty()) { //判断栈是否为空
System.out.println("Non solution");
return;
}
curNode = stack.pop(); //弹出上一次的点
continue; //继续循环
} //如果有路的话会执行到这里
stack.push(curNode); //当前点压入栈中
maze[curNode.x][curNode.y] = 2; //标记为已走
curNode = nextNode; //移动当前点
} if(nextNode.equals(out)) {
stack.push(nextNode); //将出口点添加到当前路劲中
maze[nextNode.x][nextNode.y] = 2; //标记为已走
}
System.out.println("n该迷宫的一条可行路劲为:");
System.out.println("n"+stack);
} public static void main(String[] args) {
int[][] maze = {
{ 0, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 0, 1, 1, 1, 0, 0, 0, 1, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 1, 1 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 0, 1, 0, 0 }
};
new MyMaze(maze).go();
}
}

1年前

8
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.025 s. - webmaster@yulucn.com