皇后当自强,安研星空,巴布熊猫主题曲
本文为大家分享了使用栈的迷宫算法java版，主要考察栈的使用，供大家参考，具体内容如下
主要思路如下：
我要评论
do {
if(当前位置可通过) {
标记此位置已走过;
保存当前位置并入栈;
if(当前位置为终点) {
程序结束;
}
获取下一个位置;
}
else {
if(栈非空) {
出栈；
while(当前位置方向为4且栈非空) {
标记当前位置不可走;
出栈;
}
if(当前位置的方向小于4) {
方向+1;
重新入栈;
获取下一个位置;
}
}
}
}
while (栈非空);
java代码如下：
import java.util.stack;
public class maze {
// 栈
private stack<mazenode> stack = new stack<maze.mazenode>();
// 迷宫
private int[][] maze = {
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
{1,0,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
{1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
{1,1,1,0,0,1,1,1,1,1,1,0,1,1,0,0,1},
{1,1,0,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
{1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1},
{1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1},
{1,0,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},
{1,1,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1},
{1,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
{1,0,0,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
};
// 标记路径是否已走过
private int[][] mark = new int[maze_size_x][maze_size_y];
private static final int maze_size_x = 14;
private static final int maze_size_y = 17;
private static final int end_x = 12;
private static final int end_y = 15;
private void initmark() {
for (int i = 0; i < maze_size_x; i++) {
for (int j = 0; j < maze_size_y; j++) {
mark[i][j] = 0;
}
}
}
public void process() {
initmark();
position curpos = new position(1, 1);
do {
// 此路径可走
if (maze[curpos.x][curpos.y] == 0 && mark[curpos.x][curpos.y] == 0) {
mark[curpos.x][curpos.y] = 1;
stack.push(new mazenode(curpos, 1));
// 已到终点
if (curpos.x == end_x && curpos.y == end_y) {
return;
}
curpos = nextpos(curpos, stack.peek().direction);
}
// 走不通
else {
if (!stack.isempty()) {
mazenode curnode = stack.pop();
while (curnode.direction == 4 && !stack.isempty()) {
// 如果当前位置的4个方向都已试过，那么标记该位置不可走，并出栈
mark[curnode.position.x][curnode.position.y] = 1;
curnode = stack.pop();
}
if (curnode.direction < 4) {
curnode.direction++;// 方向+1
stack.push(curnode);// 重新入栈
curpos = nextpos(curnode.position, curnode.direction);// 获取下一个位置
}
}
}
}
while(!stack.isempty());
}
public void drawmaze() {
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze[0].length; j++) {
system.out.print(maze[i][j]);
}
system.out.print("\n");
}
system.out.print("\n");
}
public void drawresult() {
initmark();
mazenode node;
while (!stack.isempty()) {
node = stack.pop();
mark[node.position.x][node.position.y] = 1;
}
for (int i = 0; i < mark.length; i++) {
for (int j = 0; j < mark[0].length; j++) {
system.out.print(mark[i][j]);
}
system.out.print("\n");
}
system.out.print("\n");
}
// 记录迷宫中的点的位置
class position {
int x;
int y;
public position(int x, int y) {
this.x = x;
this.y = y;
}
}
// 栈中的结点
class mazenode {
position position;
int direction;
public mazenode(position pos) {
this.position = pos;
}
public mazenode(position pos, int dir) {
this.position = pos;
this.direction = dir;
}
}
// 下一个位置，从右开始，顺时针
public position nextpos(position position, int direction) {
position newposition = new position(position.x, position.y);
switch (direction) {
case 1:
newposition.y += 1;
break;
case 2:
newposition.x += 1;
break;
case 3:
newposition.y -= 1;
break;
case 4:
newposition.x -= 1;
break;
default:
break;
}
return newposition;
}
public static void main(string[] args) {
maze maze = new maze();
maze.drawmaze();
maze.process();
maze.drawresult();
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持移动技术网。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
apollo与springboot集成实现动态刷新配置的教程详解
网友评论