菜单

栈的应用(走迷宫问题)

duckflew
发布于 2020-10-20 / 208 阅读
0
0

栈的应用(走迷宫问题)

栈的应用(走迷宫问题)

import lombok.AllArgsConstructor;

import java.util.Stack;

@AllArgsConstructor
class OneStep
{
    int x;
    int y;
    int direct;//方向
}

public class Maze
{
    public static void main(String[] args)
    {
        int move[][]={
                {0,1},{1,0},{0,-1},{-1,0}
        };
        Stack<OneStep> s1=new Stack<>();
        int maze[][]=
        {
            {1,1,1,1,1,1,1,1,1,1},
            {1,0,0,1,1,0,1,1,1,1},
            {1,1,0,0,0,1,1,1,1,1},
            {1,0,1,0,0,0,0,0,1,1},
            {1,0,1,1,1,0,0,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}
        };
        for (int i=0;i<maze.length;i++)
        {
            for (int j=0;j<maze[i].length;j++)
            {
                if (maze[i][j]==1)
                {
                    System.out.print("█");
                }
                else
                {
                    System.out.print("*");//零代表可以走
                }
            }
            System.out.println();
        }
        //maze[x][y]标记为-1表示已经走过了
        OneStep start=new OneStep(1,1,-1);
        maze[start.x][start.y]=-1;
        s1.push(start);
        while (!s1.empty())
        {
            OneStep oneStep = s1.pop();
            int x=oneStep.x;
            int y=oneStep.y;
            int direct = oneStep.direct+1;
            System.out.println("取出"+"("+x+","+y+")点  改变方向进行尝试");
            while (direct<4)
            {
                int nextX=x+move[direct][0];
                int nextY=y+move[direct][1];
                System.out.println("尝试:"+nextX+","+nextY);
                if (maze[nextX][nextY] == 0)
               {
                   System.out.println("("+nextX+","+nextY+")点可通 入栈 移动到这个点 标记此点已经走过了 ");
                   s1.push(new OneStep(nextX,nextY,-1));
                   x=nextX;
                   y=nextY;
                   direct=0;
                   maze[x][y]=-1;//标记已经到达的点
                   if (x==6&&y==8)
                   {
                       System.out.println("找到终点");
                       Stack<OneStep> s2=new Stack<>();
                       while (!s1.empty())
                       {
                           s2.push(s1.pop());
                       }
                       while (!s2.empty())
                       {
                           OneStep step = s2.pop();
                           System.out.println("("+step.x+","+step.y+")");
                       }
                       System.out.println("走过的路径为:('#'代表该位置被走过)");
                       //打印出走过的所有坐标位置
                       for(int i=0;i<=7;i++){
                           for(int j=0;j<=9;j++){
                               if(maze[i][j] == 1){
                                   System.out.print("█");
                               }else if(maze[i][j] == -1){
                                   System.out.print("#");
                               }else{
                                   System.out.print("*");
                               }
                           }
                           System.out.print("\n");
                       }
                       return ;
                   }
                   System.out.println("当前坐标("+x+","+y+")");
               }
               else
               {
                   direct++;
               }
            }
        }
    }
}


评论