`
东方上人
  • 浏览: 9453 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

Java堆栈实现迷宫求解

 
阅读更多
package stack;

忘记上课了,正好好在寝室看到一个迷宫求解的问题,没想到真正实现还有点复杂,下面是实现源码,不过这并非最短路径解法
  转载请注明出处,谢谢合作!
public class Maze {
  static int[][] dedale={    //用二维数组表示地图
        {0,0,0,0,0,0,0,0,0,0},
        {0,1,1,0,1,1,1,0,1,0},
        {0,1,1,0,1,1,1,0,1,0},
        {0,1,1,1,1,0,0,1,1,0},
        {0,1,0,0,0,1,1,1,1,0},
        {0,1,1,1,0,1,1,0,1,0},
        {0,1,0,1,1,1,0,1,1,0},
        {0,1,0,0,0,0,0,1,0,0},
        {0,0,1,1,1,1,1,1,1,0},
        {0,0,0,0,0,0,0,0,0,0}};
 

  public static void main(String[] args) {
    Stack<Position> stack=new Stack<Position>();
    Position start=new Position(1, 1);
    Position current=start;  //设置当前位置为起始位置
 
    do{
      if(dedale[current.x][current.y]==1&&validate(current)){  //当前位置可通(注:当前位置是标记过的位置时,路线肯定不对)
    dedale[current.x][current.y]=9;  //已经过的地方做个标记
    stack.push(current);
    if(current.x==8&&current.y==8) break;  //到达终点
   
    current=nextPosition(current);  //将当前指向下一个位置
      }else{
    if(stack.size()!=0){
      current=stack.peek();  //取出当前栈顶元素
      if(current.di>=4){    //此时此位置四个方向的路均不通时
    dedale[current.x][current.y]=4;  //留下不能通过的标记
    stack.pop();      //pop出栈顶元素
    current=stack.peek();    //获取此时栈顶元素
    continue;
        }
      if(current.di<4) current=nextPosition(current);
    }
       }  //end else
     }while(stack.size()>0);

    printPath(dedale);
   }
 
  public static void printPath(int[][] a){
for(int i=0;i<a.length;i++){
  for(int j=0;j<a[i].length;j++)
System.out.print(a[i][j]+",");
  System.out.println();
}
   }
 
  public static Position nextPosition(Position p){  //获取下一个Position
if(p.di==1){         //东
  p.di++;
  Position pos=new Position(p.x,p.y+1);
  if(!validate(pos)) return nextPosition(p);
  return pos;
}else if(p.di==2){   //南
  p.di++;
  Position pos=new Position(p.x+1,p.y);
  if(!validate(pos)) return nextPosition(p);
  return pos;  
}else if(p.di==3){   //西
  p.di++;
  Position pos=new Position(p.x,p.y-1);
  if(!validate(pos)) return nextPosition(p);
  return pos;  
}else if(p.di==4){   //北
        p.di++;
      Position pos=new Position(p.x-1,p.y);
  return pos;  
}else return null;
 
   }
 
  public static boolean validate(Position p){
    if(dedale[p.x][p.y]==9||dedale[p.x][p.y]==4){   //排除已走过的部分
      return false;
     }
    return true;
   }

}

class Position{ //表示点实体
  int x;
  int y;
  int di=1; //方向(direct)
 
  public Position(){}
 
  public Position(int x,int y){
this.x=x;
this.y=y;
   }
 
}


最终结果:
0,0,0,0,0,0,0,0,0,0,
0,9,9,0,4,4,4,0,1,0,
0,1,9,0,4,4,4,0,1,0,
0,9,9,4,4,0,0,1,1,0,
0,9,0,0,0,1,9,9,9,0,
0,9,9,9,0,9,9,0,9,0,
0,1,0,9,9,9,0,9,9,0,
0,1,0,0,0,0,0,9,0,0,
0,0,1,1,1,1,1,9,9,0,
0,0,0,0,0,0,0,0,0,0,
分享到:
评论
2 楼 东方上人 2012-11-08  
alldeath 写道
nextPosition(Position p)方法中else情况下应该return p; 

执行到else时p的di值就等于5,在main函数中do-while代码块中判断current.di>=4即证明此位置不通就会被stack弹出,也就是任何Position的di都不可能等于5   返回p和null是没有任何影响的。
1 楼 alldeath 2012-09-20  
nextPosition(Position p)方法中else情况下应该return p; 

相关推荐

    数据结构-栈的应用-迷宫求解

    在本主题“数据结构-栈的应用-迷宫求解”中,我们将探讨如何利用栈来解决迷宫路径搜索的问题。 首先,迷宫求解是一个典型的图遍历问题,可以通过深度优先搜索(DFS)或广度优先搜索(BFS)等算法来解决。在这里,...

    迷宫源代码 图形化显示堆栈变化 记录堆栈的变化

    对于“图形化显示堆栈变化”,这意味着程序不仅执行迷宫求解,还会动态展示每一步决策如何影响堆栈的状态。这可以通过创建一个可视化界面来实现,比如使用Python的tkinter库或者JavaScript的HTML5 Canvas。每当你向...

    数据结构迷宫算法(递归和非递归)

    非递归算法通常具有更好的性能,特别是在迷宫较大时,避免了递归可能导致的堆栈溢出问题。 在提供的压缩文件“迷宫问题”中,很可能包含了实现这两种算法的源代码。这些代码通常会包含以下部分: 1. **数据结构...

    java编写的递归与非递归

    在Java中,非递归通常使用循环(如`for`循环)来实现。 示例代码: ```java public static int doFactorial(int n) { int result = 1; if (n ) { return -1; } if (n == 0) { return 1; } for (int i = 1; ...

    迷宫,算法演示(数据结构课程设计)

    - **栈**:在迷宫求解过程中,栈用于实现深度优先搜索(DFS)算法,记录回溯路径。 - **队列**:广度优先搜索(BFS)算法通常用队列存储待访问的节点,确保按顺序探索所有可能的路径。 2. **算法**: - **深度...

    数据结构与算法(JAVA语言版解密)

    此外,还探索了栈和队列的应用,如进制转换、括号匹配检测和迷宫求解。 递归章节探讨了递归的概念、递归的实现与堆栈的关系,基于归纳的递归方法,以及递推关系的求解,并介绍了分治法的基本思想及其应用示例。 树...

    data_structure_java:java,数据结构,蚀,算法,arraylist,队列,堆栈,树,图,哈希,排序

    代码03:使用迷宫求解器队列和堆栈搜索迷宫,提供了10个迷宫文件,从maze1.txt到maze10.txt。 代码04:散列字符串,使用多项式将字符串转换为整数,english_word文件包含30万个单词。 代码05:BinaryTree,二进制...

    数据结构与算法(Java语言版) 周鹏 三峡大学理学院

    第四章聚焦于栈与队列的数据结构,讨论了它们的定义、抽象数据类型、存储实现以及应用示例,比如进制转换、括号匹配检测和迷宫求解。 第五章探讨了递归的概念以及递归与堆栈的关系,并介绍了基于归纳的递归和递推...

    代码二叉树迷宫.rar

    这个“二叉树迷宫”文件可能包含相关的Python、Java或C++代码示例,以及详细的步骤解释,帮助我们更好地理解和实现二叉树迷宫的构造与求解过程。如果你对数据结构和算法有兴趣,深入研究这个主题将有助于提升你的...

    JAVA语言版数据结构与算法

    - **迷宫求解**:介绍使用栈解决迷宫问题的方法。 #### 第五章:递归 - **递归与堆栈** - **递归的概念**:介绍递归的基本定义及其特点。 - **递归的实现与堆栈**:讨论递归调用时与堆栈的关系。 - **基于归纳...

    数据结构与算法 java版

    最后,书中讨论了堆栈在实现递归时的作用以及递归的几种常用算法,包括迷宫求解、括号匹配检测等。这些算法是理解算法设计策略的基础。 总体来说,《数据结构与算法 java版》为Java程序员提供了一本全面而深入的...

    JAVA算法与数据结构

    栈与队列都是基于线性表的结构,它们有特定的抽象数据类型和应用,比如括号匹配检测和迷宫求解。 递归是算法设计中的一个重要概念。在递归章节中,会介绍递归的概念、实现方式以及和堆栈的关系。此外,也会讨论基于...

    数据结构与算法(JAVA语言版)

    - **迷宫求解**:介绍如何使用栈解决迷宫问题。 #### 递归 - **递归与堆栈** - **递归的概念**:解释递归的基本定义、特点以及递归的基本原理。 - **递归的实现与堆栈**:讨论递归实现中的堆栈使用及其作用。 ...

    数据结构与算法(java语言版)

    包括栈和队列的顺序存储和链式存储实现,以及它们在进制转换、括号匹配检测和迷宫求解中的应用。本章通过实际的例子展示了这些基本数据结构的强大应用。 第五章“递归”着重讲述了递归的概念、与堆栈的关系,以及...

Global site tag (gtag.js) - Google Analytics