数据结构迷宫算法
目录
一.题目叙述二.大致题意三.解题思路四.测试结果四.源码
一.题目叙述
从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达一个新点，否则试探下一个方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。这里可以用一个栈来实现，每走一步，将该位置压入栈中，若该点无路可走，则出栈返回上一位置。
二.大致题意
用maze[m+2][n+2]来表示迷宫，maze[i][j]=0或1,等于零时通路，等1时不通路，想象迷宫四个面是墙壁，不通设为1，则可大概构造一个迷宫，如构在这里插入代码片造一个八行十列的迷宫，设定入口（1，1），出口（6，1），问有没有路径可以出去，如果有的话将路径表示出来。 int[][] maze = {{1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,0,1,1,1,1}, {1,1,0,1,0,1,1,1,1,1}, {1,0,1,0,0,0,0,0,1,1}, {1,0,1,1,1,0,1,1,1,1}, {1,1,0,0,1,1,0,0,0,1}, {1,0,1,1,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1,1,1}};
三.解题思路
一个人在（1，1）处进入迷宫，那么他在迷宫中有八个方向可以去尝试，分别是“左，右，前，后，左前，左后，右前，右后”，我们之前设定的迷宫四面都是墙则可保证迷宫内每一处都有八个方向可以试探， 他要去的的点对于当前所在点横纵坐标的变化量，可以用一个8*2的二维数组move表述，在move数组中，x表示横坐标的增量，y表示纵坐标的增量。 x y 0，1 1，1 1，0 1 , -1 0 , -1 -1 ,-1 -1 , 0 -1 , 1 同时为了防止重复的到达一个位置进入死循环，到了一点后maze[i][j]=-1,与未到达的点区分开来
四.测试结果
四.源码
package com
.stack
;
import java
.util
.Stack
;
class Step{
int x
,y
,d
;
public Step(int x
,int y
,int d
) {
this.x
= x
;
this.y
= y
;
this.d
= d
;
}
}
public class migon {
public static void main(String
[] args
) {
int[][] maze
= {
{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,1,0,1,0,1,1,1,1,1},
{1,0,1,0,0,0,0,0,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,1,0,0,1,1,0,0,0,1},
{1,0,1,1,0,0,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
int[][] move
= {
{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}
};
Stack
<Step> s
= new Stack<Step>();
int a
= path(maze
, move
, s
);
while(!s
.isEmpty()){
Step step
= s
.pop();
System
.out
.println(step
.x
+":"+step
.y
);
}
}
public static int path(int[][] maze
,int[][] move
,Stack
<Step> s
){
Step temp
= new Step(1,1,-1);
s
.push(temp
);
while(!s
.isEmpty()){
s
.pop();
if(!s
.isEmpty()){
temp
= s
.peek();
}
int x
= temp
.x
;
int y
= temp
.y
;
int d
= temp
.d
+1;
while(d
<8){
int i
= x
+ move
[d
][0];
int j
= y
+ move
[d
][1];
if(maze
[i
][j
] == 0){
temp
= new Step(i
,j
,d
);
s
.push(temp
);
x
= i
;
y
= j
;
maze
[x
][y
] = -1;
if(x
== 6 && y
== 1){
return 1;
}else{
d
= 0;
}
}else{
d
++;
}
}
}
return 0;
}
}
