?迷宫算法:
?
?一、迷宫算法:
?对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论.
?
?二、设定迷宫:用简单的二维数组.其中'A'表示入口，'B'表示出
?
口，'#'表示不通， '.'表示可以移动
?
class="java" name="code">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();
}
}
?
?
?
?七、运行效果:
?
?
?八、总结:
?总的来说，就是通过给定的点，不断遍历，得到周围可以移动的点的集合，同时记录这些点的父节点，一直遍历到出口，就遍历结束，通过出口的点得到出口的前一个点，在通过出口前一个点，得到出口前一个点的点....就这样一直到入口，这样就得到路径了。
?
相关文章
