欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

使用栈的迷宫算法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();
  }

}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。