精华内容
下载资源
问答
  • 2021-04-17 06:14:55

    源码的github地址,可以下载到本地运行

    迷宫求解

    从当前入口出发,顺某一方向前进,若则走通,则继续走,否则沿原路退回,换一个方向继续走,直到到达终点或者所有的可能的通路都走过为止

    需要一个后进先出的结构来保存入口到当前位置的路径,这个结构就是栈

    关键点在于:要判断一个位置 ,是否可通。 可通是指,可以通过,且之前没有来过

    package stack.demo;

    import java.util.ArrayList;

    import java.util.List;

    import java.util.Stack;

    /**

    * 用java提供的stack实现

    */

    public class MazePathStack {

    static class Spath { //行走的单位格子

    private int x;

    private int y;

    private int di; //方向 0 1 2 3 表示右 下 左 上

    public Spath(int x, int y, int di) {

    this.x = x;

    this.y = y;

    this.di = di;

    }

    @Override

    public boolean equals(Object obj) {

    if (super.equals(obj)) {

    return true;

    }

    if (obj instanceof Spath) {

    if ((((Spath) obj).x == this.x) && (((Spath) obj).y == this.y)) {

    return true;

    } else {

    return false;

    }

    } else {

    return false;

    }

    }

    }

    private static int[][] mg = MazePathStack.creatMG();//初始化时候生成迷宫

    private static StackspathStack = new Stack();//路径栈

    public static void main(String[] args) {

    Spath spath = new Spath(0, 1, 0); //初始坐标为入口 (0,1)方向为向右

    do {

    if (isPass(spath)) { //判断该坐标能否通行

    //判断该坐标是否是终点

    if (isEnd(spath)) {

    spathStack.push(spath);

    System.out.println("到达终点,坐标为:" + "(" + spath.x + "," + spath.y + ")");

    System.out.println("路径为");

    printAll();

    return;

    }

    //判断该坐标是否已经来过

    if (isRecord(spath)) {

    //来过 则放弃栈中最新的坐标 后退一格,换个方向重试

    spathStack.pop();

    spath = spathStack.peek();

    spath = next(spath, false);//继续下一步 换个方向

    } else {

    //没有来过 压入栈中 记录下来

    spathStack.push(spath);

    spath = next(spath, true); //继续下一步 沿原来方向

    }

    } else {

    spath = spathStack.peek(); //后退一步

    spath = next(spath, false);//换个方向 继续下一步

    }

    } while (!spathStack.empty());

    }

    private static void printAll() {

    //打印路径

    Listspaths=new ArrayList<>();

    while(!spathStack.empty()){

    spaths.add(spathStack.pop());

    }

    for (int i = spaths.size()-1; i >=0 ; i--) {

    System.out.println("("+spaths.get(i).x+","+spaths.get(i).y+")");

    }

    }

    private static Spath next(Spath spath, boolean status) {

    if (status) {

    //继续沿着原来方向

    return SpathNext(spath);

    } else {

    //换方向

    spath.di++;

    return SpathNext(spath);

    }

    }

    private static Spath SpathNext(Spath spath) {

    Spath spathNew = new Spath(spath.x, spath.y, 0);//生成新的路径节点 新的节点方向需要重置

    //方向 0 1 2 3 表示右 下 左 上

    if (spath.di == 0) { //向右走

    spathNew.y++;

    }

    if (spath.di == 1) { //向下走

    spathNew.x++;

    }

    if (spath.di == 2) {//向左走

    spathNew.y--;

    }

    if (spath.di == 3) {//向上走

    spathNew.x--;

    }

    if (spathNew.x>=0&&spathNew.x<5&&spathNew.y>=0&&spathNew.y<10){

    return spathNew;

    }

    return null;

    }

    private static Boolean isEnd(Spath spath) {

    if (spath.x == 4 && spath.y == 4) {

    return Boolean.TRUE;

    } else {

    return Boolean.FALSE;

    }

    }

    private static Boolean isRecord(Spath spath) {

    return spathStack.contains(spath);

    }

    private static Boolean isPass(Spath spath) {

    if (spath==null){

    return Boolean.FALSE;

    }

    if (mg[spath.x][spath.y] == 1) {

    return Boolean.TRUE;

    } else {

    return Boolean.FALSE;

    }

    }

    public static int[][] creatMG() {

    //创建一个迷宫

    int mg[][] = new int[5][10];

    //创建正确的路径,值为1表示可以通过

    mg[0][1] = 1;

    mg[1][1] = 1;

    mg[2][1] = 1;

    mg[2][2] = 1;

    mg[3][2] = 1;

    mg[3][3] = 1;

    mg[3][4] = 1;

    mg[4][4] = 1;

    //创建干扰路径

    mg[0][2] = 1;

    mg[0][3] = 1;

    mg[0][4] = 1;

    mg[1][4] = 1;

    mg[1][5] = 1;

    mg[1][6] = 1;

    mg[2][6] = 1;

    for (int i = 0; i < 5; i++) {

    for (int j = 0; j < 10; j++) {

    System.out.print(mg[i][j]);

    }

    System.out.println();

    }

    System.out.println();

    return mg;

    }

    }

    输出如下:

    0111100000

    0100111000

    0110001000

    0011100000

    0000100000

    到达终点,坐标为:(4,4)

    路径为

    (0,1)

    (1,1)

    (2,1)

    (2,2)

    (3,2)

    (3,3)

    (3,4)

    (4,4)

    源码的github地址,可以下载到本地运行

    更多相关内容
  • 主要为大家详细介绍了使用迷宫算法java版代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Java简单实现迷宫

    千次阅读 2019-04-16 11:39:15
    我的主要思路,首先用一个Maze类来表示迷宫上面的点,类中包含点的横纵坐标和点的值,用保存迷宫路径。从入口到出口,依次按照右 下 左 上判断四周是否是通路,如果是,将判断的点入栈,并将值置为...

    迷宫

    用0表示可以走,1表示不可以走,从左上角走到右下角,能否找到一条路,如果找到,那么打印出来路径,用2表示走过的路径

    如果找不到,那么图中尝试过的点置为 -1.

    程序运行如下

    输出如下

    我的主要思路,首先用一个Maze类来表示迷宫上面的点,类中包含点的横纵坐标和点的值,用栈保存迷宫路径。从入口到出口,依次按照右 下 左 上判断四周是否是通路,如果是,将判断的点入栈,并将值置为2,如果四周都没有通路,那么当前点出栈,将值置为-1.
    成功的条件是到达终点(即右下角的点),
    失败的条件是:
           1.开始值不是0
           2.栈为空,表示没有路径。

    实现的完整代码

    Maze.java代码

    public class Maze {
        private int x;
        private int y;
        private int value;
    
        public int getX() {
            return x;
        }
    
        public void setX(int x) {
            this.x = x;
        }
    
        public int getY() {
            return y;
        }
    
        public void setY(int y) {
            this.y = y;
        }
    
        public Maze(){
    
        }
        public Maze(int x,int y,int value){
            this.x = x;
            this.y = y;
            this.value = value;
        }
        public int getValue() {
            return value;
        }
        public void setValue(int value) {
            this.value = value;
        }
    }

    这里我没有用jdk提供的栈,自己学着写了一个简单的栈。

    MyStack.java代码

    public class MyStack {
        private final static int MAXSIZE = 10;
        private int top;
        private Maze[] mazes;
    
        public Maze getMazes(int i) {
            return mazes[i];
        }
    
        public void setMazes(Maze[] mazes) {
            this.mazes = mazes;
        }
    
        public int getTop() {
            return top;
        }
    
        public void setTop(int top) {
            this.top = top;
        }
    
        public MyStack(){
            top = -1;               //栈首下标
            mazes = new Maze[MAXSIZE];
        }
        //判栈空
        public boolean isEmpty(){
            if (top == -1){
                return true;
            }
            return false;
        }
        //栈溢出
        public boolean isFull(){
            if (top == MAXSIZE){
                return true;
            }
            return false;
        }
        //出栈
        public void pop(){
            top--;
        }
        //入栈
        public void push(Maze maze){
            top++;
            mazes[top] = maze;
        }
    
        public void printStack(){
            for (int i=0;i<=top;i++){
                System.out.println("("+mazes[i].getX()+","+mazes[i].getY()+")");
            }
        }
    }

    用MazeGame类表示一个迷宫,来保存所有的点,start()方法开始找入口,如果入口也就是(0,0)点不是0,那么没有路径,输出no way.否则表示可以进入,将(0,0)点入栈。road方法是主要实现代码,首先判栈空,如果栈是空的,那么表示没有可以走通的路径,用temp保存当前栈顶元素。startX,startY保存当前的横纵坐标。
           如果栈不空,判断当前迷宫点是否是终点,是终点游戏结束。不是终点开始判断是否有路径可以走,如果没有,该迷宫点出栈,用-1表示当前点已经走过。如果有,按照右 下 左 上的顺序依次判断,可以走,将该迷宫点入栈。

    MazeGame.java代码

    public class MazeGame {
        private Maze[][] mazes;
        public MazeGame(Maze[][] mazes){
            this.mazes = mazes;
        }
    
        public void start(){
            int startX = 0;
            int startY = 0;
            MyStack stack = new MyStack();
            mazeGamePrint();
            if (mazes[startX][startY].getValue() == 0){              // 入口是否为0
                stack.push(mazes[startX][startY]);
                mazes[startX][startY].setValue(2);                  //将以走过的路径置为2
            }else{
                System.out.println("no way");
                return ;
            }
            if(road(stack)){
                stack.printStack();
                mazeGamePrint();
            }else{
                System.out.println("no way!");
                mazeGamePrint();
            }
        }
    
        private boolean road(MyStack stack) {
            while(!stack.isEmpty()){
                int temp = stack.getTop();                              //栈顶元素
                int startX = stack.getMazes(temp).getX();
                int startY = stack.getMazes(temp).getY();
                if (startX == mazes.length-1 && startY == mazes[0].length-1){       //到达终点
                    System.out.println("路径走过的坐标");
                    return true;
                }else if (hasRoad(stack,startX,startY)){                                              //没有到达终点 且有路可走
                    if(startY<mazes[0].length-1 && mazes[startX][startY+1].getValue() == 0){       //向右
                    stack.push(mazes[startX][startY+1]);
                    mazes[startX][startY+1].setValue(2);
                    } else if (startX < mazes.length-1 && mazes[startX+1][startY].getValue() == 0){       //向下
                        stack.push(mazes[startX+1][startY]);
                        mazes[startX+1][startY].setValue(2);
                    }else if (startY > 0 && mazes[startX][startY-1].getValue() == 0){       //向左
                        stack.push(mazes[startX][startY-1]);
                        mazes[startX][startY-1].setValue(2);
                    } else if (startX > 0 && mazes[startX-1][startY].getValue() == 0){   //向上
                        stack.push(mazes[startX-1][startY]);
                        mazes[startX-1][startY].setValue(2);
                    }
                }else{
                    stack.pop();
                    mazes[startX][startY].setValue(-1);
                }
            }
            return false;
        }
    
        private boolean hasRoad(MyStack stack,int startX,int startY) {
            if (startY<mazes[0].length-1 && mazes[startX][startY+1].getValue() == 0 ||
                    startX < mazes.length-1 && mazes[startX+1][startY].getValue() == 0 ||
                    startX > 0 && mazes[startX-1][startY].getValue() == 0 ||
                    startY > 0 && mazes[startX][startY-1].getValue() == 0){
                return true;
            }
            return false;
        }
    
        public void mazeGamePrint(){
            for (int i=0;i<mazes.length;i++){
                for (int j=0;j<mazes[0].length;j++){
                    System.out.print(mazes[i][j].getValue()+" ");
                }
                System.out.println();
            }
        }
    }

    测试代码Test.java

    public class Test {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            System.out.println("请输入迷宫的行列数(m * n):");
            int m = scanner.nextInt();
            int n = scanner.nextInt();
            Maze[][] mazes = new Maze[m][n];
            System.out.println("请输入迷宫的路径");
            for (int i=0;i<m;i++){
                for (int j=0;j<n;j++){
                    mazes[i][j] = new Maze(i,j,scanner.nextInt());
                }
            }
            /*Maze[][] mazes = new Maze[][]{
                    {new Maze(0,0,0),new Maze(0,1,1),new Maze(0,2,0)},
                    {new Maze(1,0,0),new Maze(1,1,0),new Maze(1,2,0)},
                    {new Maze(2,0,1),new Maze(2,1,0),new Maze(2,2,0)}
            };*/
            MazeGame mazeGame = new MazeGame(mazes);
            mazeGame.start();
        }
    }

     

    展开全文
  • 问题描述:这时实验心理学中的一个典型的问题,心理学家吧一只老鼠从一个无顶的大盒子的入口处赶进迷宫迷宫设置很多隔壁,对前进方向形成了许多障碍,心理学家在迷宫的唯一出口处放置了一块奶酪,吸引老鼠仔迷宫中...

    问题描述:这时实验心理学中的一个典型的问题,心理学家吧一只老鼠从一个无顶的大盒子的入口处赶进迷宫。迷宫设置很多隔壁,对前进方向形成了许多障碍,心理学家在迷宫的唯一出口处放置了一块奶酪,吸引老鼠仔迷宫中寻找通路以到达出口。

    求解思想:回溯法是一种不断试探且及时纠正错误的搜索方法,下面的求解过程采用回溯法。从入口出发,按某一方向向前探索,若能走通(未走过的),即某处可以到达,则到达一个新点,否则试探下一个方向;若所有的方向均没有通路,则沿原路返回前一点,换下一个方向继续试探,直到所有可能的通路都搜索到,或找到一条通路,或无路可走又返回到入口点。这里可以用一个栈来实现,每走一步,将该位置压入栈中,若该点无路可走,则出栈返回上一位置。

    需要解决的四个问题:

    (1)表示迷宫的数据结构

    设迷宫为m行n列,利用数组maze[m][n]来表示一个迷宫,maze[i][j]=0或1,其中0表示通路,1表示不通。迷宫该数组四边都为1,代表迷宫四周都是墙。这样就可以保证每个点都有8个方向可以试探。

    入口为(1,1),出口为(6,8)

    1,1,1,1,1,1,1,1,1,1

    1,0,1,1,1,0,1,1,1,1

    1,1,0,1,0,1,1,1,1,1

    1,0,1,0,0,0,0,0,1,1

    1,0,1,1,1,0,1,1,1,1

    1,1,0,0,1,1,0,0,0,1

    1,0,1,1,0,0,1,1,0,1

    1,1,1,1,1,1,1,1,1,1

    (2)试探方向

    迷宫中间每个点都有8个方向可以试探。其增量数组可以用一个1*2的二维数组move表述,具体值如下:

    x  y

    0  0  1

    1    1     1

    2    1     0

    3    1     -1

    4    0     -1

    5    -1    -1

    6    -1    0

    7    -1    1

    在move数组中,x表示横坐标的增量,y表示纵坐标的增量。

    (3)栈中存放元素的设计

    栈中所存放的元素应该包含所到达的每点的坐标以及从该点沿哪个方向向下走的。可以用一个类表示:

    1 classStep{2 intx,y,d;3 public Step(int x,int y,intd) {4 this.x = x;//横坐标

    5 this.y = y;//纵坐标

    6 this.d = d;//方向

    7 }8 }

    (4)防止重复到达某点而发生死循环

    可以用两种方法来实现,第一种就是另外设置一个标志数组mark[m][n],它的所有元素初始都为0,一旦到达某点,则设置该点的标志位1,下次试探的时候就不再走这点了。第二种就是当到达某点的时候,使maze[i][j]置为-1,以便区别为达到的点,同样也可以防止走重复点的作用。

    具体代码如下:

    1 packagecom.stack;2

    3 importjava.util.Stack;4

    5 /**

    6 * 用栈来实现迷宫的求解7 *@author刘玲8 *9 */

    10

    11 classStep{12 intx,y,d;13 public Step(int x,int y,intd) {14 this.x = x;//横坐标

    15 this.y = y;//纵坐标

    16 this.d = d;//方向

    17 }18 }19

    20 public classMazeTest {21

    22 public static voidmain(String[] args) {23 //迷宫定义

    24 int[][] maze = {{1,1,1,1,1,1,1,1,1,1},25 {1,0,1,1,1,0,1,1,1,1},26 {1,1,0,1,0,1,1,1,1,1},27 {1,0,1,0,0,0,0,0,1,1},28 {1,0,1,1,1,0,1,1,1,1},29 {1,1,0,0,1,1,0,0,0,1},30 {1,0,1,1,0,0,1,1,0,1},31 {1,1,1,1,1,1,1,1,1,1}};32 int[][] move = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};33 Stack s = new Stack();34 Stack s1 = new Stack();35 int a =path(maze, move, s);36 while(!s.isEmpty()){37 Step step =s.pop();38 System.out.println(step.x+":"+step.y);39 }40 }41 public static int path(int[][] maze,int[][] move,Stacks){42 Step temp = new Step(1,1,-1); //起点

    43 s.push(temp);44 while(!s.isEmpty()){45 temp =s.pop();46 int x =temp.x;47 int y =temp.y;48 int d = temp.d+1;49 while(d<8){50 int i = x + move[d][0];51 int j = y + move[d][1];52 if(maze[i][j] == 0){ //该点可达

    53 temp = new Step(i,j,d); //到达新点

    54 s.push(temp);55 x =i;56 y =j;57 maze[x][y] = -1; //到达新点,标志已经到达

    58 if(x == 6 && y == 8){59 return 1; //到达出口,迷宫有路,返回1

    60 }else{61 d = 0; //重新初始化方向

    62 }63 }else{64 d++; //改变方向

    65 }66 }67 }68 return 0;69 }70

    71 }

    输出结果如下:

    6:8

    5:8

    5:7

    5:6

    4:5

    3:5

    3:4

    3:3

    2:2

    由于栈是后进先出的,所以结果应该从下面看起(2,2)->(3,3)->(3,4)->(3,5)->(4,5)->(5,6)->(5,7)->(5,8)->(6,8)

    有运行结果可以看出来,栈中所存储的就是迷宫的一条通路。

    上面那个代码有一点点小问题,非常感谢问题的提出者,修改如下:

    1 packagecom.stack;2

    3 importjava.util.Stack;4

    5 /**

    6 * 用栈来实现迷宫的求解7 *@author刘玲8 *9 */

    10

    11 classStep{12 intx,y,d;13 public Step(int x,int y,intd) {14 this.x = x;//横坐标

    15 this.y = y;//纵坐标

    16 this.d = d;//方向

    17 }18 }19

    20 public classMazeTest {21

    22 public static voidmain(String[] args) {23 //迷宫定义

    24 int[][] maze = {{1,1,1,1,1,1,1,1,1,1},25 {1,0,1,1,1,0,1,1,1,1},26 {1,1,0,1,0,1,1,1,1,1},27 {1,0,1,0,0,0,0,0,1,1},28 {1,0,1,1,1,0,1,1,1,1},29 {1,1,0,0,1,1,0,0,0,1},30 {1,0,1,1,0,0,1,1,0,1},31 {1,1,1,1,1,1,1,1,1,1}};32 int[][] move = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};33 Stack s = new Stack();34 int a =path(maze, move, s);35 while(!s.isEmpty()){36 Step step =s.pop();37 System.out.println(step.x+":"+step.y);38 }39 }40 public static int path(int[][] maze,int[][] move,Stacks){41 Step temp = new Step(1,1,-1); //起点

    42 s.push(temp);43 while(!s.isEmpty()){44 //temp = s.pop(); 这样写是有问题的,不能将出栈的元素作为当前位置,应该将栈顶元素作为当前位置

    45 s.pop(); //如果路走不通就出栈

    46 if(!s.isEmpty()){47 temp = s.peek(); //将栈顶元素设置为当前位置

    48 }49 int x =temp.x;50 int y =temp.y;51 int d = temp.d+1;52 while(d<8){53 int i = x + move[d][0];54 int j = y + move[d][1];55 if(maze[i][j] == 0){ //该点可达

    56 temp = new Step(i,j,d); //到达新点

    57 s.push(temp);58 x =i;59 y =j;60 maze[x][y] = -1; //到达新点,标志已经到达

    61 if(x == 6 && y == 1){62 return 1; //到达出口,迷宫有路,返回1

    63 }else{64 d = 0; //重新初始化方向

    65 }66 }else{67 d++; //改变方向

    68 }69 }70 }71 return 0;72 }73

    74 }

    展开全文
  • 展开全部importjava.io.File;importjava.io.FileNotFoundException;importjava.util.HashSet;importjava.util.LinkedList;importjava.util.List;importjava.util.Scanner;publicclassTest{publicstaticvoidm...

    展开全部

    import java.io.File;

    import java.io.FileNotFoundException;

    import java.util.HashSet;

    import java.util.LinkedList;

    import java.util.List;

    import java.util.Scanner;

    public class Test {

    public static void main(String[] args) throws FileNotFoundException {

    62616964757a686964616fe78988e69d8331333335306333Scanner input = new Scanner(new File("Maze2tong.txt"));

    int row = 0;

    char[][] Mazemap = new char[12][58];

    while (input.hasNext()) {

    String line = input.nextLine();

    for (int column = 0; column <= line.length() - 1; column++) {

    char c = line.charAt(column);

    Mazemap[row][column] = c;

    }

    row++;

    }

    for (int i = 0; i 

    for (int j = 0; j 

    System.out.print(Mazemap[i][j]);

    }

    System.out.print("\n");

    }

    LinkedList> trace = new LinkedList>();

    System.out.println(maze(Mazemap, trace));

    System.out.println(trace);

    }

    public static boolean maze(char[][] maze,

    List> trace) {

    LinkedList> path = new LinkedList>();

    HashSet> traverse = new HashSet>();

    for (int i = 0; i 

    for (int j = 0; j 

    if (maze[i][j] == 'S') {

    path.add(new TwoTuple(i, j));

    }

    }

    }

    while (!path.isEmpty()) {

    TwoTuple temp = path.pop();

    if (traverse.contains(temp)) {

    continue;

    } else if (maze[temp.first][temp.second] == 'F') {

    trace.add(temp);

    return true;

    } else if (!traverse.contains(temp)) {

    if (temp.second + 1 

    && maze[temp.first][temp.second + 1] != 'W')

    path.add(new TwoTuple(temp.first,

    temp.second + 1));

    if (temp.second - 1 > 0

    && maze[temp.first][temp.second - 1] != 'W')

    path.add(new TwoTuple(temp.first,

    temp.second - 1));

    if (temp.first + 1 

    && maze[temp.first + 1][temp.second] != 'W')

    path.add(new TwoTuple(temp.first + 1,

    temp.second));

    if (temp.first - 1 > 0

    && maze[temp.first - 1][temp.second] != 'W')

    path.add(new TwoTuple(temp.first - 1,

    temp.second));

    traverse.add(temp);

    trace.add(temp);

    }

    }

    trace.clear();

    return false;

    }

    }

    class TwoTuple {

    public final A first;

    public final B second;

    public TwoTuple(A a, B b) {

    first = a;

    second = b;

    }

    @Override

    public int hashCode() {

    return first.hashCode() + second.hashCode();

    }

    @Override

    public boolean equals(Object obj) {

    if (!(obj instanceof TwoTuple)) {

    }

    return obj instanceof TwoTuple && first.equals(((TwoTuple) obj).first)

    && second.equals(((TwoTuple) obj).second);

    }

    public String toString() {

    return "(" + first + ", " + second + ")";

    }

    } // /:-

    import java.io.File;

    import java.io.FileNotFoundException;

    import java.util.LinkedList;

    import java.util.Scanner;

    class MyPoint

    {

    public boolean visited=false;

    public int parentRow=-1;

    public int parentColumn=-1;

    public final char content;

    public int x;

    public int y;

    public MyPoint(char c,int x,int y)

    {

    this.content = c;

    this.x = x;

    this.y = y;

    }

    }

    public class Maze

    {

    public static MyPoint[][] getMazeArray(){

    Scanner input = null;

    MyPoint[][] mazemap = new MyPoint[12][58];

    try {

    input = new Scanner(new File("Maze2tong.txt"));

    int row = 0;

    while (input.hasNext()) {

    String line = input.nextLine();

    for (int column = 0; column <= line.length() - 1; column++) {

    char c = line.charAt(column);

    MyPoint point = new MyPoint(c,row,column);

    mazemap[row][column] = point;

    }

    row++;

    }

    input.close();

    } catch (FileNotFoundException e) {

    e.printStackTrace();

    }

    return mazemap;

    }

    public static boolean tomRun(MyPoint[][] maze,MyPoint end)

    {

    int x = maze.length;

    int y = maze[0].length;

    LinkedList stack=new LinkedList();

    for (int i = 0; i 

    for (int j = 0; j 

    if (maze[i][j].content == 'S') {

    stack.push(maze[i][j]);

    maze[i][j].visited=true;

    }

    }

    }

    boolean result=false;

    while(!stack.isEmpty())

    {

    MyPoint t=stack.pop();

    //System.out.println("pop point:"+t.x+" "+t.y+" value:"+maze[t.x][t.y]);

    if(t.content == 'F')

    {

    result=true;

    end.x = t.x;

    end.y = t.y;

    break;

    }

    if(t.x-1 > 0 && maze[t.x-1][t.y].visited==false && maze[t.x-1][t.y].content != 'W')

    {

    stack.push(maze[t.x-1][t.y]);

    maze[t.x-1][t.y].parentRow=t.x;

    maze[t.x-1][t.y].parentColumn=t.y;

    maze[t.x-1][t.y].visited=true;

    }

    if(t.x + 1 

    {

    stack.push(maze[t.x+1][t.y]);

    maze[t.x+1][t.y].parentRow=t.x;

    maze[t.x+1][t.y].parentColumn=t.y;

    maze[t.x+1][t.y].visited=true;

    }

    if(t.y - 1 > 0 && maze[t.x][t.y - 1].visited==false && maze[t.x][t.y-1].content != 'W')

    {

    stack.push(maze[t.x][t.y-1]);

    maze[t.x][t.y-1].parentRow=t.x;

    maze[t.x][t.y-1].parentColumn=t.y;

    maze[t.x][t.y-1].visited=true;

    }

    if( t.y + 1 

    {

    stack.push(maze[t.x][t.y+1]);

    maze[t.x][t.y+1].parentRow=t.x;

    maze[t.x][t.y+1].parentColumn=t.y;

    maze[t.x][t.y+1].visited=true;

    }

    }

    return result;

    }

    public static void show(int x,int y,MyPoint[][] visited)

    {

    if(visited[x][y].parentRow==-1)

    {

    System.out.println("["+x+","+y+"]");

    return;

    }

    show(visited[x][y].parentRow,visited[x][y].parentColumn,visited);

    System.out.println("->"+"["+x+","+y+"]");

    }

    public static void main(String[] args)

    {

    MyPoint[][] maze = getMazeArray();

    MyPoint point = new MyPoint('c',1,1);

    if(tomRun(maze,point))

    {

    System.out.println("逃生路径如下:");

    show(point.x,point.y,maze);

    }

    else

    System.out.println("无法走出迷宫!");

    }

    }

    WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

    WSOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOWOOOOOOW

    WWOOOOOOOOOOOOOWWWWWWWWWWWWWOOOOOOOOOOWWWWWWWWWWWWWOOOOOOW

    WWWWWWOOOOOOOOOOOOWWWWWWWOOOOOOOOOOOOWWWWWWWWWWWWWWWWOOOOW

    WOOOOOOWWWWWWWWWWWWWWOOOOOOOOOOOWWWWWWWWWWWWWWWWWWWWWWWWWW

    WOOOOWWWWWWWOOOOOOWWWWOOOOOOWWWWWWWWWWWOOOOWWWWWWWWWOWWWWW

    WOOOWWWWWWWWWWWWOOWWWWWWWWWWWWOOOOOOOOOOOOWWWWWWWWWOOOOOWW

    WOOWWWWWWWWWWWWWOOWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWWOOOW

    WOWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWOOW

    WOWWWWWWWWWWWWWOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWWWWWWWWOOW

    WOOOOOOOOOOOOOOOOWWWWOOOOOOOOWWWWWWWOOOOOOWWWWWWWWWWWWWWFW

    WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

    WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

    WSOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOWOOOOOOW

    WWOOOOOOOOOOOOOWWWWWWWWWWWWWOOOOOOOOOOWWWWWWWWWWWWWOOOOOOW

    WWWWWWOOOOOOOOOOOOWWWWWWWOOOOOOOOOOOOWWWWWWWWWWWWWWWWOOOOW

    WOOOOOOWWWWWWWWWWWWWWOOOOOOOOOOOWWWWWWWWWWWWWWWWWWWWWWWWWW

    WOOOOWWWWWWWOOOOOOWWWWOOOOOOWWWWWWWWWWWOOOOOOOOOOOOOOOOOWW

    WOOOWWWWWWWWWWWWOOWWWWWWWWWWWWOOOOOOOOOOOOWWWWWWWWWOOOOOWW

    WOOWWWWWWWWWWWWWOOWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWWOOOW

    WOWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWOOW

    WOWWWWWWWWWWWWWOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWWWWWWWWOOW

    WOOOOOOOOOOOOOOOOWWWWOOOOOOOOWWWWWWWOOOOOOWWWWWWWWWWWWWWFW

    WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

    展开全文
  • 运用求解迷宫问题

    2021-04-18 07:13:10
    设计4.防止重复到某一点, 以免发生死循环, 将走过的点初始化为 - 1,即maze[x][y] = -1.5.迷宫算法的求解思想:3.代码1.题目问题描述:设置迷宫为mn的二维数组,起点坐标为(1,1),中点坐标为(m,n),0为通路,1为...
  • JAVA 解决迷宫问题

    2022-01-21 17:01:03
    有一个迷宫,1是墙壁不可走,0是可以走的路.从入口出发,规定只能通过向上、向下、向左和向右方向进行走动,问如何才能找到一条到达出口的通路。 {1, 1, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 1, 0, 0, 0, 1, 1, 1}, {1, ...
  • 一、概述迷宫问题:一只老鼠从一个无顶盖的大盒子入口处进入迷宫,经过层层障碍到达唯一的出口处吃到奶酪。递归与回溯:1.递归:若一个对象部分的包含它自己,或用它自己给自己定义,则称这个对象是递归的;若一个...
  • 最近,博主已经开始重温数据结构啦,记得我们以前学习这里的时候,老师会用队列来实现迷宫最优解的寻找,氮素呢,博主就是这么可爱,博主就是想试试用来找一下。在实现之前让我们先来复习一下的特点:first in ...
  • 数据结构(Java)实践作业迷宫参考书本使用结构实现的
  • [c++]代码库#include #include #include #...#define INIT_SIZE 100 //存储空间初始分配量#define SIZE_ADD 10 //存储空间分配增量#define MAXLEN 10 //迷宫大小struct Coord{int r;int c;bool operator == (con...
  • 主要介绍了java 实现迷宫回溯算法示例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • 1.(Stack)这两天复习了一下stack的...2.基于迷宫求解基于的算法应用很多,比如代码编译、算式求解和迷宫求解等等。迷宫求解这个问题以前也碰到过,那时候果断是觉得不明觉厉。今天终于自己实现了一把。用...
  • 迷宫问题() 有一个迷宫地图,有一些可达的位置,也有一些不可达的位置(障碍、墙壁、边界)。从当前位置到下一个位置只能通过向上(或者向右、或者向下、或者向左)走一步来实现,从起点出发,如何找到一条到达...
  • 超详解的迷宫问题(Java版)

    千次阅读 多人点赞 2021-05-19 10:25:33
    迷宫问题问题描述算法实现use Stack代码展示recursion代码展示 问题描述 给定一个M*N 的迷宫图、入口与出口、行走规则。...考虑使用,从当前位置分别向四个方向寻找,可行的点,如果有可行的点就入栈,若无
  • 迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫,从入口开始,可以按DRRURRDDDR 的顺序通过迷宫, 一共 10 步。其中 D、U、L、R 分别表示向...
  • 使用数据结构 (Stack)来实现一种低级的迷宫寻路的功能。低级是因为无法判断路径是不是最短的。这里使用的结构如图 (这图我选择死亡...)注意结构体里DataType的实际含义,是另外一个结构体,用于储存二维位置x,y...
  • maze.txt(*代表可通,#代表不通)~~~/*** 1 从maze.txt读入迷宫* 2 从入口坐标(1,1)寻找到出口的通路* 3 显示迷宫中数据* 0 退出程序* MazeApp* 创建人:guxiaohao* 时间:2017年10月29日-上午9:56:52* @version 1.0.0...
  • 摘要: 使用的数据结构及相应的回溯算法实现迷宫创建及求解,带点JavaGUI 的基础知识。难度: 中级迷宫问题是的典型应用,通常也与回溯算法连用。 回溯算法的基本描述是:(1) 选择一个起始点;(2) 如果已达...
  • 思路:解决迷宫求解的问题,从入口出发,顺某...因此,在求迷宫通路的算法中要应用“”的思想假设“当前位置”指的是“在搜索过程中的某一时刻所在图中某个方块位置”,则求迷宫中一条路径的算法的基本思想是:若...
  • 实现迷宫

    2014-11-03 22:28:27
    供C++初学者参考,代码没什么难度,放网上也可以帮帮人,对初学者有帮助的
  • java迷宫课程设计.zip

    2021-06-08 22:06:33
    通过java实现的迷宫课程设计。分成算法部分和界面部分,算法部分涉及到迷宫生成算法,深度优先,广度优先,运用了和队列等容器。界面部分采用javafx实现。有显示迷宫路线,更改迷宫大小,展示迷宫解谜动画过程。...
  • 给定任意设定的迷宫,左上角为入口,有下角为出口,判断该迷宫是否存在通路,若有,则非递归求解迷宫的一条通路以及三元组路径,并且递归求解迷宫的所有通路以及对应的三元组路径;若无,则提示该迷宫无路。
  • 项目三 Java开发迷宫游戏

    千次阅读 2021-12-14 11:33:50
     迷宫由一个一个格子组成,要求从入口到出口只有一条路径.  通过树实现是比较容易的,从根节点到每一个子节点都只有一条路径。假设入口是根节点,出口是树中某个子节点,那么,从根节点到该子节点的路径肯定是...
  • JAVA实现走迷宫

    2022-01-07 00:34:12
    import java.util.Stack; public class Maze { //保存迷宫 private int[][] maze; //入口与出口 private Location in; private Location out; //保存路径 private Stack<Location> stack; //初始化 ...
  • 然后按先上后下先左后右尝试走下一步,走完之后把点位信息存入,然后继续初始化下一点的信息,如此轮回,当走到死路的时候 出栈回退,一直回退到有下一条出路的点位,继续走下去。 胜利判断方法:当栈顶元素 位置...
  • 迷宫问题 非递归(java版)

    千次阅读 2017-10-31 15:47:10
    怎么利用的特点来解决这个问题? 在迷宫行走怎么更改迷宫的方向? 怎么寻找迷宫路径?以及怎么才算找到迷宫路径? 二、思路通过上面的问题关键,在脑中可以构造一个大体的思路: 首先创建一个迷宫maze,对于迷宫...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,872
精华内容 1,148
关键字:

java栈迷宫

java 订阅