java实现find迷宫路径

网友投稿 688 2022-05-30

迷宫项目实现设计文档

项目介绍:

java实现find迷宫路径

一个网格迷宫由n行m列的单元格组成,每个大院个要么是空地(用0表示),要么是障碍物(用1表示)。你的任务是找一条从起点到终点的移动序列,其中只能上下左右移动到相邻单元格。任何时候都不能在有障碍物的单元格中,也不能走到迷宫之外。起点为左上角和终点右下角。

项目功能:

解决迷宫路径查找问题,寻找一条从左上角迷宫入口到右下角迷宫出口的一条有效路径,0代表可走,1代表不能行走,找到请输出最终的迷宫和路径信息,找不到请输出不存在有效路径。

项目所用知识点:

采用Java面向对象思想,二维数组以及非递归栈进行实现

项目实现思路:

定义一个迷宫节点类型(MazeNode)的二维数组

初始化每个格子中的value值。给二维数组每个格子存放对象。对象的value值只能为0(当前格子可以走)或者1(当前格子不能走)

创建围墙,可以有效防止越界问题。根据当前节点周围四个方向格子中的value值,判断当前节点的上下左右四个方向是否可走(0是可走,1不可走)。

开始走迷宫。采用栈操作,记录行走的路径,将元素入栈,判断当前栈顶元素的哪个方向可走,将其中一个可走方向进行入栈操作,直到右下角元素停止。栈中保存走过的路径。 注意: 如果遇到走入死胡同问题,此时需要将是栈顶元素并且栈顶元素的四个方向都不能行走,此时将其出栈,选择新方向再次入栈,直到右下角元素停止。

项目实现 :

Maze类

import java.util.Scanner; public class Maze {     private MazeNode[][] mazenode;     private int row ;//行     private int colum;//列     public Maze(){     }     public void innode(){//添加迷宫路径;         Scanner scanner=new Scanner(System.in);         System.out.println("请输入迷宫行数和列数");         row=scanner.nextInt()+2;//为后面加围墙         colum=scanner.nextInt()+2;         System.out.println("请输入迷宫路径:");         mazenode=new MazeNode[row][colum];         build(mazenode);//创建一个row行colum列的mazenode并且把value值都给1         for(int i=1;i

mazenode类

public class MazeNode {     public int index1;     public int index2;     public int value;     public MazeNode(int value,int index1,int index2) {         this.value=value;         this.index1=index1;//下标1         this.index2=index2;//下标2     }     //改变找个点的值为2    public void changeValue(MazeNode[][] mazeNode,int index1,int index2){         mazeNode[index1][index2].value=2;    }    //判断左边是否可走     public boolean left(MazeNode[][] mazeNode,int index1,int index2){        if(mazeNode[index1][index2].value==0){         return true;        }return false;     }     //判断上边是否可走     public boolean up(MazeNode[][] mazeNode,int index1,int index2){         if(mazeNode[index1][index2].value==0){             return true;         }return false;     }     //判断右边是否可走     public boolean right(MazeNode[][] mazeNode,int index1,int index2){         if(mazeNode[index1][index2].value==0){             return true;         }return false;     }     //判断下边是否可走     public boolean down(MazeNode[][] mazeNode,int index1,int index2){         if(mazeNode[index1][index2].value==0){             return true;         }return false;     } }

MyStake类//栈

import java.util.Arrays; import java.util.EmptyStackException; public class MyStack {     private PuzzleValue[]array2;     private MazeNode[]array;     private int size;     private final int INITSIZE=10;     public MyStack(){         array=new MazeNode[INITSIZE];         array2=new PuzzleValue[INITSIZE];     }     //查找栈内是否存在此路径     public  boolean contain(MyStack stack,MazeNode[][] mazeNode,int index1,int index2){         for(int i=0;i>1));         }else {         array[size]=mazeNode;         size++;         }     }     //出栈     public void pop(MazeNode mazeNode){         if(size==0){             return;         }else{             array[size]=null;             size--;         }     }     //获得栈顶元素     public MazeNode gettop(){         return array[size-1];     }     //改变栈内的value值     public void toRoute(){         for(int i=0;i

Java

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:BPMN工作流的基本概念!详解工作流框架Activiti的服务架构和组件
下一篇:第十一届蓝桥杯 2020年省赛真题 (Java 大学C组 )
相关文章