迷宫算法

 迷宫算法:

 

 一、迷宫算法:

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

 

 二、设定迷宫:用简单的二维数组.其中'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();  

    }

}

 

 

 

 七、运行效果:

 

 

 八、总结:

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