`
Cb123456
  • 浏览: 65991 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

迷宫算法

    博客分类:
  • java
阅读更多

 迷宫算法:

 

 一、迷宫算法:

 对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论.

 

 二、设定迷宫:用简单的二维数组.其中'A'表示入口,'B'表示出

 

口,'#'表示不通, '.'表示可以移动

 

char[][] maze =

    {{'#','#','#','#','B','#','#','#','#','#','#','#'},

    {'#','#','#','#','.','.','.','.','#','#','#','#'},

    {'#','#','#','#','.','#','#','#','#','.','.','#'},

    {'#','.','.','.','.','#','#','#','#','#','.','#'},

    {'#','.','#','#','#','#','#','.','#','#','.','#'},

    {'#','.','#','#','#','#','#','.','#','#','.','#'},

    {'#','.','#','#','.','.','.','.','.','.','.','#'},

    {'#','.','#','#','.','#','#','#','.','#','.','#'},

    {'#','.','.','.','.','#','#','#','.','#','.','#'},

    {'#','#','.','#','.','#','#','#','.','#','.','A'},

    {'#','#','.','#','#','#','.','.','.','#','#','#'},

    {'#','#','#','#','#','#','#','#','#','#','#','#'}};

 

 

     

 

  三、设定一个cell类,用来描述迷宫中的每个小格子

 

class Cell//内部类

    {

        private int row;//迷宫中小格子的行
        private int col;//迷宫中小格子的列
        private Cell from;//指向父节点
        public Cell(int row, int col, Cell from)

        {
            this.row = row;
            this.col = col;
            this.from = from;

        }

    }

 

 

 四、开始遍历:

 

public void resolve()

    
    {   
    	

        Set<Cell> set = new HashSet<Cell>();

        set.add(new Cell(9,11,null)); 
        for(;;)

        {
            Set<Cell> set1 = new HashSet<Cell>();
            Cell a = colorCell(set, set1);

            if(a!=null)

            {

                while(a!=null)//这样啊,此时的a就是出口的点.

                {

                	
                    maze[a.row][a.col] = '+';//标出通路路径

                    a =a.from;//并把当前节点的父节点,标记为+
                    

                }
                
                maze[9][11] = 'A';

                break;

            }
            set = set1;

        }      

    }

      给定开始点(9,11,null),也就是A的坐标,而且A是没有父类的,所以A的父节点为null,其中colorCell(set,set1),是为了得到当前给定cell周围的cell是不是通的,如果是通的,就把这个cell加到set里面,同时记录这个cell的父节点,然后在遍历这个set,一直到出口为止。

 

 

 五、输出结果.

 由第四步得到的set,也就是一条从入口到出口的cell的集合,通过cell.from不断得到后一个cell的前一个cell,这样路径就得到了,

 

 

 六、完整示例:

package sss;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class MiGongSuanFa

{
   
	boolean ifFirst=false;
    class Cell//内部类

    {

        private int row;//迷宫中小格子的行
        private int col;//迷宫中小格子的列
        private Cell from;//指向父节点
        public Cell(int row, int col, Cell from)

        {
            this.row = row;
            this.col = col;
            this.from = from;

        }

    }

       

    char[][] maze =

    {{'#','#','#','#','B','#','#','#','#','#','#','#'},

    {'#','#','#','#','.','.','.','.','#','#','#','#'},

    {'#','#','#','#','.','#','#','#','#','.','.','#'},

    {'#','.','.','.','.','#','#','#','#','#','.','#'},

    {'#','.','#','#','#','#','#','.','#','#','.','#'},

    {'#','.','#','#','#','#','#','.','#','#','.','#'},

    {'#','.','#','#','.','.','.','.','.','.','.','#'},

    {'#','.','#','#','.','#','#','#','.','#','.','#'},

    {'#','.','.','.','.','#','#','#','.','#','.','#'},

    {'#','#','.','#','.','#','#','#','.','#','.','A'},

    {'#','#','.','#','#','#','.','.','.','#','#','#'},

    {'#','#','#','#','#','#','#','#','#','#','#','#'}};

   

    public void show()

    {
    	if (!ifFirst) {
    		System.out.println("生成的迷宫:");
    		ifFirst=true;
		}else{
			
			System.out.println("找到的道路是:");
			ifFirst=false;
			
		}
        
        for(int i=0; i<maze.length; i++)

        {

            for(int j=0; j<maze[i].length; j++)

       System.out.print(" " + maze[i][j]);

            System.out.println();

        }

    }

   

    //把与from集合中相邻的可染色节点染色,被染色节点记入 dest

    //一旦发现出口将被染色,则返回当前的“传播源”节点

    public Cell colorCell(Set<Cell> from, Set<Cell> dest)

    {    
        
        

        Iterator<Cell> it = from.iterator();

        while(it.hasNext())

        {   

            Cell a = it.next();

            Cell[] c = new Cell[4];

            c[0] = new Cell(a.row-1, a.col, a); //向上

            c[1] = new Cell(a.row, a.col-1, a); //向左

            c[2] = new Cell(a.row+1, a.col, a); //向下

            c[3] = new  Cell(a.row, a.col+1, a); //向右

                       

            //遍历4个孩子
            for(int i=0; i<4; i++)

            {

                if(c[i].row < 0 || c[i].row >= maze.length)continue;

                if(c[i].col < 0 || c[i].col >= maze[0].length)continue;

               

                char x = maze[c[i].row][c[i].col];

                if(x=='B') return a;

                if(x=='.')

                {

                    maze[c[i].row][c[i].col] = '?';//对可通过路径进行标记
                   
                    dest.add(c[i]);
                    

                }

            }
            
        }
       
        return null;

    }

   

    public void resolve()

    
    {   
    	

        Set<Cell> set = new HashSet<Cell>();

        set.add(new Cell(9,11,null)); 
        for(;;)

        {
            Set<Cell> set1 = new HashSet<Cell>();
            Cell a = colorCell(set, set1);

            if(a!=null)

            {

                while(a!=null)//这样啊,此时的a就是出口的点.

                {

                	
                    maze[a.row][a.col] = '+';//标出通路路径

                    a =a.from;//并把当前节点的父节点,标记为+
                    

                }
                
                maze[9][11] = 'A';

                break;

            }
            set = set1;

        }      

    }

   

    public static void main(String[] args)

    {

        MiGongSuanFa m = new MiGongSuanFa();

        m.show();

        m.resolve();

        m.show();  

    }

}

 

 

 

 七、运行效果:


 

 

 八、总结:

 总的来说,就是通过给定的点,不断遍历,得到周围可以移动的点的集合,同时记录这些点的父节点,一直遍历到出口,就遍历结束,通过出口的点得到出口的前一个点,在通过出口前一个点,得到出口前一个点的点....就这样一直到入口,这样就得到路径了。

 

  • 大小: 37.4 KB
1
0
分享到:
评论

相关推荐

    优化的迷宫算法

    《优化的迷宫算法》 迷宫算法是计算机科学中的一种经典问题,它涉及路径搜索、图论和算法设计等多个领域。在这个特定的优化版本中,我们关注的是如何有效地找到迷宫中的最短路径。在实际应用中,这种算法不仅在游戏...

    迷宫算法(Java)

    在IT领域,迷宫算法是一种常见的问题解决方法,它涉及到路径寻找、图遍历和决策树等概念。本文将深入探讨使用Java实现迷宫算法,特别是结合搜索回溯策略,并带有方向倾向性。 首先,我们要理解迷宫问题的基本框架。...

    迷宫算法迷宫算法

    迷宫算法是计算机科学中的一种路径寻找问题,它在游戏设计、图形学、人工智能和算法竞赛等领域有着广泛的应用。在解决迷宫问题时,我们通常需要设计或选择一种算法来帮助“虚拟角色”或者程序从起点找到终点。下面将...

    c语言实现的迷宫算法

    在编程领域,迷宫算法是一种常见且有趣的问题解决方法,主要应用于路径搜索、游戏设计以及图形处理等场景。本文将详细解析用C语言实现的迷宫算法,通过深入理解其核心思想,帮助读者掌握此类算法的基本原理和实现...

    数据结构 迷宫算法

    迷宫算法是数据结构应用的一个有趣实例,通常用于解决路径寻找问题。在这个实验中,我们将利用栈这一数据结构来解决迷宫问题。 栈是一种线性数据结构,遵循“后进先出”(LIFO)原则,类似于日常生活中的堆叠物品。...

    迷宫算法来自动生成迷宫

    迷宫算法是一种在计算机科学中常见的问题,主要应用于游戏开发、路径规划等领域。自动生成迷宫的算法有很多种,包括深度优先搜索(DFS)、广度优先搜索(BFS)、Prim算法、Kruskal算法以及瓦片法等。这些算法各有...

    只能老鼠走迷宫算法

    ### 智能老鼠走迷宫算法解析 #### 一、引言 随着人工智能与机器人技术的快速发展,智能机器人的应用场景越来越广泛。其中,“智能老鼠”作为一种能够在复杂环境中自主导航的机器人,尤其受到关注。这类机器人通常...

    C语言数据结构 迷宫算法

    在IT领域,尤其是在编程和算法设计中,"C语言数据结构 迷宫算法"是一个具有挑战性和趣味性的主题。这个主题涉及到C语言编程、数据结构和算法应用,特别是动态堆栈的使用。以下是对这些知识点的详细解释: 1. **...

    VC/c++平台队列实现迷宫算法

    在IT领域,迷宫算法是数据结构和算法应用的一个经典示例,它通常用于路径寻找问题。本主题将深入探讨如何在VC/C++环境中利用队列数据结构来实现迷宫算法。队列是一种先进先出(FIFO)的数据结构,非常适合解决这类...

    智能图形化迷宫算法

    智能图形化迷宫算法是一种将计算机科学中的算法与图形用户界面相结合的技术,旨在解决迷宫求解问题。在这个程序中,用户可以自定义绘制迷宫图形,程序随后会通过特定的算法找出从起点到终点的最短路径。下面将详细...

    迷宫算法的实现及其代码 用栈的思想

    在IT领域,迷宫算法是一种常见的路径搜索问题,它涉及到数据结构和算法设计。本文将深入探讨迷宫算法的实现,特别是使用栈这种数据结构来解决这类问题。我们将讨论迷宫的设置、方向选择、绝境与墙的判断,以及如何...

    【stl】 迷宫算法

    ### STL简易迷宫算法解析 本文将详细介绍一个基于STL(标准模板库)实现的简易迷宫算法。此算法不仅涵盖了迷宫的生成过程,还包括了寻找从入口到出口路径的基本逻辑。 #### 标题解释:“【stl】迷宫算法” 标题中...

    迷宫算法c语言经典代码

    迷宫算法c语言代码。迷宫算法c语言经典代码迷宫算法c语言经典代码

    破解迷宫算法(需要预先下载随即迷宫生成算法)

    下载该资源前请确认已下载前置资源(随机迷宫生成算法),使用时先使用随即迷宫生成算法生成迷宫.txt文件,再将该文件复制到破解迷宫算法C文件同目录下才可使用。请确保头文件中的raw值和column值与随机迷宫生成算法...

    C#实现迷宫算法(使用堆栈)

    在本文中,我们将深入探讨如何使用C#编程语言实现迷宫算法,并重点讲解利用堆栈数据结构来解决这一问题。迷宫算法是一个经典的路径搜索问题,通常用于游戏开发、路径规划和其他需要找到从起点到终点最短路径的应用...

    VC 解析迷宫算法的一个例子源代码.rar

    《VC解析迷宫算法:一个源代码实例的深度探索》 迷宫算法是计算机科学中的一个重要领域,尤其在游戏开发和路径规划中有着广泛应用。本文将深入探讨一个基于VC++的迷宫生成算法实例,旨在为SDK初级学者提供学习参考...

    数据结构课程设计C语言迷宫算法

    在这个具体的“数据结构课程设计C语言迷宫算法”项目中,我们聚焦于利用C语言来实现迷宫问题的解决方案。C语言以其高效、灵活的特点,常被用于编写底层算法和数据结构实现。 迷宫问题是一个经典的图论问题,通常...

    迷宫算法实现(C++)

    在IT领域,迷宫算法是一种常见的问题解决方法,特别是在游戏开发、路径规划和图形处理中。C++作为一款强大的编程语言,提供了丰富的工具和库来实现这类算法。本篇文章将深入探讨如何用C++实现迷宫算法,并将其应用于...

    数据结构迷宫算法

    学习数据结构时候编写的迷宫算法, 欢迎批评指正相互学习!

    数据结构 迷宫算法的详细实现

    在本项目中,我们探讨的是基于严蔚敏教授的经典教材《数据结构》中的一种迷宫算法的实现。迷宫算法通常用于解决路径寻找问题,如在复杂的网格环境中找到从起点到终点的最短路径。在这个程序中,我们将重点讨论如何...

Global site tag (gtag.js) - Google Analytics