迷宫问题能够看做是在“图”中求解：已知的两个节点是否连通，以及求某个连通的通路。能够通过图的深度优先遍历求解。
import java.util.HashSet;
import java.util.Set;
class Pos{
public int i;
public int j;
public Pos(int i,int j){
this.i=i;
this.j=j;
}
public int hashCode(){
return i*100+j;
}
public boolean equals(Object x){
if(x instanceof Pos){
Pos p=(Pos)x;
return p.i==i&&p.j==j;
}
return false;
}
}
@SuppressWarnings("unchecked")
public class Maze {
private char[][] data;
private Pos entry;
private Pos exit;
private Set solve=new HashSet();
private void getStdInput(){
String[] x={
"####B#######",
"####....####",
"####.####..#",
"#....#######",
"#.#####.##.#",
"#.#####.##.#",
"#.##.......#",
"#.##.###.#.#",
"#....###.#.#",
"##.#.###.#.A",
"##.###...###",
"############",
};
data=new char[x.length][];
for(int i=0;i data[i]=x[i].toCharArray(); for(int j=0;j if(data[i][j]=='A')entry=new Pos(i,j); if(data[i][j]=='B')exit=new Pos(i,j); } } } private void show(){ for(int i=0;i for(int j=0;j char c=data[i][j]; if(c=='.'&&solve.contains(new Pos(i,j)))c='x'; System.out.print(c+""); } System.out.println(); } } private boolean go(Pos cur,Set path){ if(cur.equals(exit))return true; path.add(cur); Pos[] t={ new Pos(cur.i,cur.j-1), new Pos(cur.i,cur.j+1), new Pos(cur.i-1,cur.j), new Pos(cur.i+1,cur.j), }; for(int i=0; i try { //不是墙壁，且不在路径中的点 if(data[t[i].i][t[i].j]!='#'&&path.contains(t[i])==false) if(go(t[i],path)){//递归。找到true，即找到终点 solve.add(cur); return true;//通过邻居已经找到了通路 } } catch (Exception e) { //这里用try catch是个小技巧，以防数组下标越界，由于可能某个点不都有上下左右点，一旦异常，默默的过去 } } return false; } private void go(){ Set path=new HashSet(); solve=new HashSet(); go(entry,path); } public static void main(String[] args) { Maze maze=new Maze(); maze.getStdInput();//获得迷宫的初始状态。包含墙壁。通路，入口，出口等设置 maze.show();//显示当前状态 maze.go();//解决 System.out.println("---------"); maze.show(); } }
发表评论