使用栈的迷宫算法java版代码

本文为大家分享了使用栈的迷宫算法java版,主要考察栈的使用,供大家参考,具体内容如下

主要思路如下:

 do {
  if(当前位置可通过) {
    标记此位置已走过;
    保存当前位置并入栈;
    if(当前位置为终点) {
      程序结束;
    }
    获取下一个位置;
  }
  else {
    if(栈非空) {
      出栈;
      while(当前位置方向为4且栈非空) {
        标记当前位置不可走;
        出栈;
      }
      if(当前位置的方向小于4) {
        方向+1;
        重新入栈;
        获取下一个位置;
      }
    }
  }
}
while (栈非空);

java代码如下:

import java.util.Stack;

public class Maze {

  // 栈
  private Stack<MazeNode> stack = new Stack<Maze.MazeNode>();
  // 迷宫
  private int[][] maze = {
    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
    {1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
    {1,0,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
    {1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
    {1,1,1,0,0,1,1,1,1,1,1,0,1,1,0,0,1},
    {1,1,0,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
    {1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1},
    {1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1},
    {1,0,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1},
    {1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},
    {1,1,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1},
    {1,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
    {1,0,0,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
  };
  // 标记路径是否已走过
  private int[][] mark = new int[MAZE_SIZE_X][MAZE_SIZE_Y];

  private static final int MAZE_SIZE_X = 14;
  private static final int MAZE_SIZE_Y = 17;
  private static final int END_X = 12;
  private static final int END_Y = 15;

  private void initMark() {
    for (int i = 0; i < MAZE_SIZE_X; i++) {
      for (int j = 0; j < MAZE_SIZE_Y; j++) {
        mark[i][j] = 0;
      }
    }
  }

  public void process() {
    initMark();
    Position curPos = new Position(1, 1);

    do {
      // 此路径可走
      if (maze[curPos.x][curPos.y] == 0 && mark[curPos.x][curPos.y] == 0) {
        mark[curPos.x][curPos.y] = 1;
        stack.push(new MazeNode(curPos, 1));
        // 已到终点
        if (curPos.x == END_X && curPos.y == END_Y) {
          return;
        }
        curPos = nextPos(curPos, stack.peek().direction);
      }
      // 走不通
      else {
        if (!stack.isEmpty()) {
          MazeNode curNode = stack.pop();
          while (curNode.direction == 4 && !stack.isEmpty()) {
            // 如果当前位置的4个方向都已试过,那么标记该位置不可走,并出栈
            mark[curNode.position.x][curNode.position.y] = 1;
            curNode = stack.pop();
          }
          if (curNode.direction < 4) {
            curNode.direction++;// 方向+1
            stack.push(curNode);// 重新入栈
            curPos = nextPos(curNode.position, curNode.direction);// 获取下一个位置
          }
        }
      }
    }
    while(!stack.isEmpty());
  }

  public void drawMaze() {
    for (int i = 0; i < maze.length; i++) {
      for (int j = 0; j < maze[0].length; j++) {
        System.out.print(maze[i][j]);
      }
      System.out.print("\n");
    }
    System.out.print("\n");
  }

  public void drawResult() {
    initMark();
    MazeNode node;
    while (!stack.isEmpty()) {
      node = stack.pop();
      mark[node.position.x][node.position.y] = 1;
    }
    for (int i = 0; i < mark.length; i++) {
      for (int j = 0; j < mark[0].length; j++) {
        System.out.print(mark[i][j]);
      }
      System.out.print("\n");
    }
    System.out.print("\n");
  }

  // 记录迷宫中的点的位置
  class Position {
    int x;
    int y;

    public Position(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }

  // 栈中的结点
  class MazeNode {
    Position position;
    int direction;

    public MazeNode(Position pos) {
      this.position = pos;
    }
    public MazeNode(Position pos, int dir) {
      this.position = pos;
      this.direction = dir;
    }
  }

  // 下一个位置,从右开始,顺时针
  public Position nextPos(Position position, int direction) {
    Position newPosition = new Position(position.x, position.y);
    switch (direction) {
    case 1:
      newPosition.y += 1;
      break;
    case 2:
      newPosition.x += 1;
      break;
    case 3:
      newPosition.y -= 1;
      break;
    case 4:
      newPosition.x -= 1;
      break;
    default:
      break;
    }
    return newPosition;
  }

  public static void main(String[] args) {
    Maze maze = new Maze();
    maze.drawMaze();
    maze.process();
    maze.drawResult();
  }

}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

您可能感兴趣的文章:

  • java实现单词搜索迷宫游戏
  • Java编写迷宫小游戏
  • Java遗传算法之冲出迷宫
  • Java实现走迷宫回溯算法
  • java图的深度优先遍历实现随机生成迷宫
(0)

相关推荐

  • Java实现走迷宫回溯算法

    以一个M×N的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍.设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论. (1) 根据二维数组,输出迷宫的图形. (2) 探索迷宫的四个方向:RIGHT为向右,DOWN向下,LEFT向左,UP向上,输出从入口到出口的行走路径. 例子: 左上角(1,1)为入口,右下角(8,9)为出口. 可使用回溯方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进:否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通

  • java图的深度优先遍历实现随机生成迷宫

    最近经常在机房看同学在玩一个走迷宫的游戏,比较有趣,自己也用java写一个实现随机生成迷宫的算法,其实就是一个图的深度优先遍历算法.基本思想就是,迷宫中的每个点都有四面墙,然后呢. 1.从任意一点开始访问(我的算法中固定是从(0,0)点开始),往四个方向中的随机一个访问(每访问到一个可访问的点,就去掉该点的那个方向的墙),被访问点继续以这种方识向下进行访问. 2.对每个被访问的点都被标识为已访问,当一个点对某个方向进行访问时我们首先会判断被访问点是否已被访问,或者触到边界.如果该点四个方向皆已访

  • Java遗传算法之冲出迷宫

    遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法.它能解决很多问题,比如数学方程的最大最小值,背包问题,装箱问题等.在游戏开发中遗传算法的应用也十分频繁,不少的游戏 AI 都利用遗传算法进行编码. 就个人理解,遗传算法是模拟神奇的大自然中生物"优胜劣汰"原则指导下的进化过程,好的基因有更多的机会得到繁衍,这样一来,随着繁衍的进行,生物种群会朝着一个趋势收敛.而生物繁衍过程中的基因杂交和变异会给种群提供更好的基因序列

  • java实现单词搜索迷宫游戏

    本文实例讲述了java实现单词搜索迷宫游戏.分享给大家供大家参考.具体分析如下: 我们在杂志上,经常能够看到找单词的小游戏,在一个二维表格中,存在各种字母,我们可以从八个方向找单词.这个用计算机处理十分方便,但是,算法的好坏很重要,因为要是用蛮力算法实现,那么耗费的时间是不可想象的. 这是数据结构与问题求解Java语言描述一书中给的实现思路 完整代码如下,注释写的很明白了 import java.io.BufferedReader; import java.io.FileReader; impo

  • Java编写迷宫小游戏

    缘起: 去年(大三上学期)比较喜欢写小游戏,于是想试着写个迷宫试一下. 程序效果: 按下空格显示路径: 思考过程: 迷宫由一个一个格子组成,要求从入口到出口只有一条路径. 想了一下各种数据结构,似乎树是比较合适的,从根节点到每一个子节点都只有一条路径.假设入口是根节点,出口是树中某个子节点,那么,从根节点到该子节点的路径肯定是唯一的. 所以如果能构造一棵树把所有的格子都覆盖到,也就能够做出一个迷宫了. 另外还要求树的父节点和子节点必须是界面上相邻的格子. 在界面显示时,父节点和子节点之间共用的边

  • 使用栈的迷宫算法java版代码

    本文为大家分享了使用栈的迷宫算法java版,主要考察栈的使用,供大家参考,具体内容如下 主要思路如下: do { if(当前位置可通过) { 标记此位置已走过; 保存当前位置并入栈; if(当前位置为终点) { 程序结束; } 获取下一个位置; } else { if(栈非空) { 出栈: while(当前位置方向为4且栈非空) { 标记当前位置不可走; 出栈; } if(当前位置的方向小于4) { 方向+1; 重新入栈; 获取下一个位置; } } } } while (栈非空); java代码

  • 详解直接插入排序算法与相关的Java版代码实现

    直接插入排序 直接插入排序的思路很容易理解,它是这样的: 1.把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的. 2.从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置. 3.重复上述过程直到最后一个元素被插入有序子数组中. 4.排序完成. 示例: 思路很简单,但代码并非像冒泡排序那么好写.首先,如何判断合适的位置?大于等于左边.小于等于右边?不行,很多边界条件需要考虑,而且判断次数太多.其次,数组中插入元素,必然需要移动大量元素,如何控制它们

  • K均值聚类算法的Java版实现代码示例

    1.简介 K均值聚类算法是先随机选取K个对象作为初始的聚类中心.然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心.聚类中心以及分配给它们的对象就代表一个聚类.一旦全部对象都被分配了,每个聚类的聚类中心会根据聚类中现有的对象被重新计算.这个过程将不断重复直到满足某个终止条件.终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小. 2.什么是聚类 聚类是一个将数据集中在某些方面相似的数据成员进行分类组织

  • Java版超大整数阶乘算法代码详解-10,0000级

    当计算超过20以上的阶乘时,阶乘的结果值往往会很大.一个很小的数字的阶乘结果就可能超过目前个人计算机的整数范围.如果需求很大的阶乘,比如1000以上完全无法用简单的递归方式去解决.在网上我看到很多用C.C++和C#写的一些关于大整数阶乘的算法,其中不乏经典但也有很多粗糙的文章.数组越界,一眼就可以看出程序本身无法运行.转载他人文章的时候,代码倒是仔细看看啊.唉,粗糙.过年了,在家闲来蛋疼,仔细分析分析,用Java实现了一个程序计算超大整数阶乘.思想取自网上,由我个人优化和改进. 这个方法采用"数

  • Java实现warcraft java版游戏的示例代码

    目录 前言 主要需求 功能截图 代码实现 启动入口 ModelAttacker类 ModelUnit类 总结 前言 致敬经典的warcraft,<warcraft java版>是一款即时战略题材单机游戏,采用魔兽原味风格和机制.收集资源,建造防御工事,消灭所有敌军. 人类:洛丹伦人类联盟自兽人首次穿过黑暗之门时便告成立.他们坚韧不拔,勇敢无畏,身穿坚甲,手握利刃,英勇迎敌. 兽人:兽人是一个粗犷而坚韧的种族,他们身穿简单的皮毛和带有尖刺的皮甲,以肆意凶狠的战斗风格而闻名. 用java语言实现,

  • 详解堆排序算法原理及Java版的代码实现

    概述 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,

  • Java版给爱人表白的玫瑰花程序代码

    1 书写表白语句的frame(渐入功能) package com.wanju.blessing; import java.awt.Color; import java.awt.Container; import java.awt.Dimension; import java.awt.Font; import java.awt.Graphics; import java.awt.Image; import java.awt.Toolkit; import java.awt.event.MouseA

  • Java版数据结构插入数据时遇到的结点为空的问题详解

    在演示Java版数据结构与算法教材中的头插法代码时遇到了空结点问题 . 先上代码. 链表类 import java.util.Scanner; public class ListLinked<T> { ListLinkedNode<Integer> head=new ListLinkedNode<Integer>();//声明头结点 //添加结点 public void addFromHead(int e){ ListLinkedNode<Integer>

  • Java版坦克大战游戏源码示例

    整理文档,搜刮出一个Java版坦克大战游戏的代码,稍微整理精简一下做下分享. package tankwar; import java.awt.Color; import java.awt.Font; import java.awt.Graphics; import java.awt.event.KeyEvent; import java.awt.event.KeyListener; import java.io.File; import java.io.FileInputStream; imp

  • Java版C语言版简单使用静态语言实现动态数组的方法

    动态语言相对于静态语言的一个优势,就是数组可以不需要预先确定大小,对于一些数组长度不确定的场景下是非常有用的.像PHP,只需要声明一下数组 $arr = array() 然后就可以直接 $arr[] = 1,$arr[] = 2,$arr[] = 3...这样一直加元素了,删除一个元素就直接使用unset($arr[1]),元素的空间就被释放了,而C和JAVA原生的数组就没有这么方便,声明的时候就必须先预先确定长度,由编译器分配相应的内存空间.不过通过一些巧妙的做法,也是可以实现一样的功能的,这

随机推荐