本demo使用三个类
一个test类
一个自定义的stack类
一个自定义的queue类
可以实现的功能：
1.对于一个写在文本文件中的迷宫，能够将其转换为二维数组用广度优先搜索实现查找最短路径
2.可以不定义迷宫的入口和出口，能自动查找到出入口
前提是要有一个对应路径的.txt文件
这里举个例子吧,我的是”f:/1号迷宫(0,18).txt”路径下
运行结果
示例代码
注释写的很详细，这里就不多赘述了
package com;
import java.io.bufferedreader;
import java.io.file;
import java.io.filereader;
/**迷宫测试
* 1号迷宫(0,18).txt
*2号迷宫(0,1).txt
*/
public class test {
public static void main(string[] args) throws exception {
test test = new test();
//通过文件输入流得到二维数组
char[][] arr = test.getfile("f:/1号迷宫(0,18).txt");
system.out.println("二维数组的长度为:"+arr[0].length);
int deep = test.getdeepbychar(arr);
system.out.println("二维数组的深度为:"+deep);
//找到入口位置
int [] begin = test.begin(arr);
system.out.println("入口位置:("+begin[0]+","+begin[1]+")");
//找到出口位置
int [] end = test.end(arr,deep);
system.out.println("出口位置:("+end[0]+","+end[1]+")");
system.out.println("=================================打印二维数组============================================");
//打印二维数组
test.printarr(arr,deep);
system.out.println("=================================最短路径图展示===========================================");
//求最短路径图
int[][] bfs = test.bfs(arr,begin,end,deep);
for (int i = 0; i < deep; i++) {
for (int j = 0; j < bfs[0].length; j++) {
system.out.print(bfs[i][j]+"\t");
}
system.out.println();
}
system.out.println("================================最短路径===============================================");
//根据最短路径图得到最短路径
int[][] result = test.getloaderfrommap(bfs, begin, end, deep);
//得到result的深度
int deep1 = test.getdeepbyint(result);
for (int i = 0; i < deep1; i++) {
system.out.println("("+result[i][0]+","+result[i][1]+")\t");
}
}
//求最短路径图
public int[][] bfs(char [][] arr, int [] begin, int [] end,int deep) {
//移动的四个方向
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};
//d二维数组用来表示路径图
int[][] d = new int [deep][arr[0].length];
//储存未进行处理的节点,这里linkedlist实现了deque,deque又继承了queue
queue1<int[]> que = new queue1<>();
// queue<int []> que = new linkedlist<>();
//将所有的位置都初始化为最大
for(int i = 0; i < d.length; i++) {
for(int j = 0; j < d[0].length; j++) {
d[i][j] = -1;
}
}
//将起始点放入队列
que.offer(begin);
//将起始点最短路径设为0
d[begin[0]][begin[1]] = 0;
//一直循环直到队列为空
while(!que.isempty()) {
//取出队列中最前端的点
int [] current = que.poll();
//如果是终点则结束
if(current[0] == end[0] && current[1] == end[1]){
break;
}
//四个方向循环
for(int i = 0; i < 4; i++) {
//试探
int nx = current[0] + dx[i];
int ny = current[1] + dy[i];
//判断是否可以走
if(nx >= 0 && nx < deep && ny >= 0 && ny < d[0].length && arr[nx][ny] == '0' && d[nx][ny] == -1) {
//如果可以走，则将该点的距离加1
d[nx][ny] = d[current[0]][current[1]] + 1;
//并将该点放入队列等待下次处理
int[] c = {nx, ny};
que.offer(c);
}
}
}
return d;
}
//根据最短路径图得到最短路径
private int [][] getloaderfrommap(int [][] map,int [] begin,int [] end,int deep) {
int k = 0;//标志位
//创建二维数组最终正序存储结果
int[][] resultlist = new int[map.length * map.length][2];
//result数组存储每个正确位置的下标
int[] result;
//创建一个栈,从出口开始把位置压入栈，之后再遍历栈就是正的迷宫顺序
stack1<int[]> stack = new stack1<>();
//先把出口压入栈
stack.push(end);
//移动的四个方向
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};
//已知出口和入口,从出口逆推入口
//只要出口没有和入口下标重合，就一直循环
while(true){
//获得栈中最顶层元素，不取出
int[] current = stack.peek();
for (int i = 0; i < 4; i++) {
//试探
int nx = current[0] + dx[i];
int ny = current[1] + dy[i];
//如果当前节点不是入口节点，就继续向前追溯
if(map[current[0]][current[1]] != map[begin[0]][begin[1]]){
//判断是否可以走
if (nx >= 0 && nx < deep && ny >= 0 && ny < map[0].length && map[nx][ny] != -1) {
//从后往前追溯，前一个数值一定比后一个小1
if(map[nx][ny] == map[current[0]][current[1]]-1){
//如果可以走,将此节点入栈
result = new int[]{nx, ny};
stack.push(result);
}
}
}else{
k++;
break;
}
}
//k是为了打破最外层循环，在比较map[current[0]][current[1]] != map[begin[0]][begin[1]]时
//如果当前节点等于入口时，就应该打破循环，但是while和for是两重循环，所以加一个标志位再打破一次
if(k != 0){
break;
}
}
//取出栈中元素赋给resultlist
int len = stack.length();
for(int i = 0;i < len;i++){
result = stack.pop();
resultlist[i][0] = result[0];
resultlist[i][1] = result[1];
}
return resultlist;
}
//把文件中的二进制转换为二维数组
private char[][] getfile (string pathname) throws exception {
file file = new file(pathname);
//文件不存在时抛出异常
if (!file.exists())
throw new runtimeexception("not file!");
//字符缓冲输入流//缓冲流是处理流，要先new一个字符输入流
bufferedreader br = new bufferedreader(new filereader(file));
//字符串str用来存储一行数据
string str;
//初始化一个二维数组
char[][] arr = new char[110][];
//x用来记录读取的行数
int x = 0;
while ((str = br.readline()) != null) {
x++;
//把字符串变成字符数组存储
char[] carr = str.tochararray();
//把一行字符数组加入到二维数组中
arr[x - 1] = carr;
}
br.close();
return arr;
}
//找到入口位置
private int[] begin ( char[][] arr){
//存储起点的下标begin[0]=x,begin[1]=y
int[] begin = new int[2];
//用stringbuffer把数组转为字符串，方便找到其中的元素
stringbuffer s = new stringbuffer();
for (int i = 0; i < arr[0].length; i++) {
s.append(arr[0][i]);
}
//如果入口在第一行
//判断下标是否存在
if (s.indexof("0") != -1) {
begin[0] = 0;
begin[1] = s.indexof("0");
return begin;
} else {
//如果入口在第一列
for (int i = 0; i < arr.length; i++) {
if (arr[i][0] == '0') {
begin[0] = i;
begin[1] = 0;
return begin;
}
}
}
return begin;
}
//找到出口位置
private int[] end ( char[][] arr, int deep){
//存储出口的下标end[0]=x,end[1]=y
int[] end = new int[2];
//出口在最后一列上 //18是第二个表的深度
for (int i = 0; i < deep; i++) {
//最后一列上找到出口
if (arr[i][arr[0].length - 1] == '0') {
end[0] = i;
end[1] = arr[0].length - 1;
return end;
}
}
//出口在最后一行上
for (int i = 0; i < arr.length; i++) {
//最后一行上找到出口 //deep为最后一行的下标
if (arr[deep - 1][i] == '0') {
end[0] = deep - 1;
end[1] = i;
return end;
}
}
return end;
}
/**
* 由于二维数组刚创建时的默认行数为110，但是实际存储不到110，在对二维数组进行遍历得到实际有效深度时
* 就会抛出数组下标越界异常，发生越界异常可认为到达二维数组的深度边缘，此时的深度就是有效深度
* 将异常捕获，返回此时深度就可以得到二维数组的有效深度
*/
//得到二维数组有效深度
private int getdeepbychar ( char[][] arr){
int y = 0;//深度
for (int i = 0; i < arr.length; i++) {
//由于i可能越界，当i越界时就认为到达最底部,返回当前y值
try {
//如果第一列那行数据不为1或0，就认为此行无效
if (arr[i][0] != '1' && arr[i][0] != '0') {
break;
}
} catch (exception e) {
return y;
}
y++;
}
return y;
}
//得到二维整形数组有效深度
private int getdeepbyint ( int[][] arr){
int y = 0;//深度
for (int i = 0; i < arr.length; i++) {
//如果遇到(0,0)的，认为已经失效
if (arr[i][0] == 0 && arr[i][1] == 0) {
break;
}
y++;
}
return y;
}
//打印二维数组
private void printarr ( char[][] arr, int deep){
for (int i = 0; i < arr[0].length; i++) {
for (int j = 0; j < deep; j++) {
try {
system.out.print(arr[i][j] + "\t");
} catch (exception e) {
}
}
system.out.println();
}
}
}
/**
* 队列
* @param <e>
*/
class queue1<e> {
private e[] arr;//使用数组表示一个队列
private int size;//size表示队列中有效元素个数
private int putindex=-1;//putindex表示从队列中放数的索引始终从队首取，并且取得索引始终为arr[0]
//有参构造
protected queue1(int initsize){
if(initsize < 0){
throw new illegalargumentexception("参数错误");
}
arr = (e[])new object[initsize];
size = 0;
}
//无参构造，默认10个长度大小
protected queue1(){
this(110);
}
//入队
protected void offer(e e){
if(size == arr.length) {
throw new arrayindexoutofboundsexception("无法进行push操作，队列已满");
}
arr[++putindex] = e;
size++;
}
//判断队列是否为空
protected boolean isempty(){
return size == 0?true:false;
}
//出队
protected e poll() {
if (size == 0) {
throw new arrayindexoutofboundsexception("this queue is empty!当前队列为空");
}
e tmp = arr[0];
//后面的元素向前移动
for (int i = 0; i < size - 1; i++) {
arr[i] = arr[i + 1];
}
arr[size - 1] = null;
putindex--;
size--;
return tmp;
}
}
/**
* 栈
* @param <e>
*/
class stack1<e> {
private int maxsize;//最大长度
private int top = -1;//栈顶指针，初始指向-1
private e[] data;//数组代替栈存放元素
//初始化栈大小
protected stack1(int maxsize){
if(maxsize > 0){
this.maxsize = maxsize;
//data数组对象也要初始化大小
data = (e[])new object[maxsize];
}else{
throw new illegalargumentexception("初始化栈大小失败，参数不合法");
}
}
//默认初始化大小为10
protected stack1(){
//调用有参构造，传入10
this(10);
}
//入栈
protected boolean push(e e){
//先判断栈是否已满
if(top == maxsize-1){
//扩容
this.resize();
}
//先top++,再top = e
data [++top] = e;
return true;
}
//判断栈是否为空
protected boolean isempty(){
return top == -1;
}
//得到栈的长度
protected int length(){
return top+1;
}
//出栈
protected e pop(){
//先判断栈是否为空
if(top == -1){
throw new illegalargumentexception("栈当前为空");
}
else{
e e = data[top];
//先top = null,再top--
data[top--] = null;
return e;
}
}
//查看栈顶元素
protected e peek(){
//先判断栈是否为空
if(top == -1){
throw new illegalargumentexception("栈当前为空");
}else{
return data[top];
}
}
//栈扩容，默认扩容为原来的一倍
protected void resize(){
int newsize = maxsize*2;
e[] newdata = (e[])new object[newsize];
for (int i = 0;i < data.length;i ++){
newdata[i] = data[i];
}
//刷新最大长度
maxsize = newsize;
//再把newdata赋值给data数组
data = newdata;
}
}
总结
到此这篇关于如何利用java实现走迷宫程序的文章就介绍到这了,更多相关java走迷宫程序内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！
黄山市民网：https://www.huangshanshimin.com/
