使用栈的迷宫算法java版代码
程序员文章站
2023-12-02 19:41:34
本文为大家分享了使用栈的迷宫算法java版,主要考察栈的使用,供大家参考,具体内容如下
主要思路如下:
do {
if(当前位置可通过) {...
本文为大家分享了使用栈的迷宫算法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(); } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
上一篇: Java实现的贷款金额计算功能示例