首页 > 代码库 > 迷宫问题用‘图’求解

迷宫问题用‘图’求解

2024-07-03 15:57:05   223人阅读

迷宫问题可以看做是在“图”中求解：已知的两个节点是否连通，以及求某个连通的通路。可以通过图的深度优先遍历求解。

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=http://www.mamicode.com/new char[x.length][];
for(int i=0;i<data.length;i++){
data[i]=x[i].toCharArray();
for(int j=0;j<data[i].length;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<data.length;i++){

for(int j=0;j<data[i].length;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<t.length;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();
}


}


联系
我们