0
我有这个类和解决迷宫的代码，但我不明白为什么解决方案是这样写的......它甚至不使用图...找到完美的迷宫路径，使用图结构
这里是GraphNode：http://pastebin.com/DMprKQAN
以下是图表：http://pastebin.com/ueCWqPww
迷宫类：
public class Lavirint {
Graph<String> g;
int start_node;
int end_node;
Hashtable<String, Integer> h;
public Lavirint() {
h = new Hashtable<String, Integer>();
g= null;
}
void generateGraph(int rows, int columns, String[] in) {
int num_nodes = 0;
String key;
for(int i=1; i<rows-1; i++){
for(int j=1; j<columns-1; j++){
if(in[i].charAt(j)!='#'){
key = i+","+j;
h.put(key, num_nodes);
if(in[i].charAt(j)=='S')
start_node = num_nodes;
if(in[i].charAt(j)=='E')
end_node = num_nodes;
num_nodes++;
}
}
}
g = new Graph<String>(num_nodes);
int x, y;
// Generating neighbours matrix
for(int i=1; i<rows-1; i++){
for(int j=1; j<columns-1; j++){
if(in[i].charAt(j)!='#'){
if(in[i].charAt(j-1)!='#'){
x = h.get(i+","+j); y = h.get(i+","+(j-1));
g.addEdge(x, y);
}
if(in[i].charAt(j+1)!='#'){
x = h.get(i+","+j); y = h.get(i+","+(j+1));
g.addEdge(x, y);
}
if(in[i-1].charAt(j)!='#'){
x = h.get(i+","+j); y = h.get((i-1)+","+j);
g.addEdge(x, y);
}
if(in[i+1].charAt(j)!='#'){
x = h.get(i+","+j); y = h.get((i+1)+","+j);
g.addEdge(x, y);
}
}
}
}
}
void findPath() {
boolean visited[] = new boolean[g.num_nodes];
for (int i = 0; i < g.num_nodes; i++)
visited[i] = false;
visited[start_node] = true;
Stack<Integer> s = new Stack<Integer>();
s.push(start_node);
int pom,pom1;
while (!s.isEmpty() && s.peek()!=end_node) {
pom = s.peek();
pom1 = pom;
for (int i = 0; i < g.num_nodes; i++) {
if(g.adjacent(pom,i)==1){
pom1 = i;
if(!visited[i])
break;
}
}
if(!visited[pom1]){
visited[pom1] = true;
s.push(pom1);
}
else
s.pop();
}
Stack<Integer> os = new Stack<Integer>();
while(!s.isEmpty())
os.push(s.pop());
while(!os.isEmpty()) {
String t=null;
Iterator<Entry<String,Integer>> it=(h.entrySet()).iterator();
int i=os.pop();
while(it.hasNext()) {
Entry<String, Integer> entry=it.next();
if (entry.getValue()==i) {
System.out.println(entry.getKey());
break;
}
}
}
}
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Lavirint l = new Lavirint();
String pom = br.readLine();
String[] ppom = pom.split(",");
int rows = Integer.parseInt(ppom[0]);
int columns = Integer.parseInt(ppom[1]);
String[] in = new String[rows];
for (int i = 0; i < rows; i++)
in[i] = br.readLine();
l.generateGraph(rows, columns, in);
l.findPath();
}
}
我不明白为什么G时raph正在生成GraphNode.info是空的，只有边被标记，因为它已完成，找到路径（）有奇怪的解决方案... 所有我想知道的是这是好的或正确的方法，如果我解决这个迷宫在GraphNode中使用Char作为信息变量将是不好的解决方案？
测试用例：
1.
6,6
######
#S# E#
# # ##
# ##
######
######
答：
1,1
2,1
3,1
3,2
3,3
2,3
1,3
1,4
2.
8,8
########
# S####
# ## #
# # #
###### #
##### #
#####E##
########
答：
1,3
1,2
1,1
2,1
3,1
3,2
3,3
3,4
2,4
2,5
2,6
3,6
4,6
5,6
5,5
6,5