【短学期算法作业】用Java写迷宫问题(栈)

分类专栏:
用Java写数据结构

文章标签:
Java
原创

题目介绍

迷宫问题(栈) 有一个迷宫地图,有一些可达的位置,也有一些不可达的位置(障碍、墙壁、边界)。从当前位置到下一个位置只能通过向上(或者向右、或者向下、或者向左)走一步来实现,从起点出发,如何找到一条到达终点的通路。 用二维矩阵来模拟迷宫地图,1代表该位置不可达,0代表该位置可达。每走过一个位置就将地图的对应位置标记,以免重复。找到通路后打印每一步的坐标,最终到达终点位置。 Input

题目思路

利用广度搜索法,遍历能找到的结点并标记,然后用另外一个数组来记录走过的路径。

具体代码

package com.dreamchaser;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 迷宫问题(栈)
 *
 */
public class test1 {
    int m=8;
    int n=8;
    static int[][] maze={{1,1,1,1,1,1,1,1,1,1},

            {1,0,0,1,0,0,0,1,0,1},

            {1,0,0,1,0,0,0,1,0,1},

            {1,0,0,0,0,1,1,0,0,1},

            {1,0,1,1,1,0,0,0,0,1},

            {1,0,0,0,1,0,0,0,0,1},

            {1,0,1,0,0,0,1,0,0,1},

            {1,0,1,1,1,0,1,1,0,1},

            {1,1,0,0,0,0,0,0,0,1},

            {1,1,1,1,1,1,1,1,1,1}};


    public static void main(String[] args) {
        Queue<Node> queue=new LinkedList<Node>();
        queue.add(new Node(1,1,null));
        while (!queue.isEmpty()){
            Node node=queue.poll();
            Node temp;
            //将相邻的可达点加入队列
            do {
                temp=find(node);
                if (temp!=null){
                    queue.add(temp);
                }
            }while (temp!=null);
            if (node.x==8&&node.y==8){
                print(node);
            }
        }

    }

    /**
     * 递归输出
     * @param node
     */
    private static void print(Node node) {
        if (node.pre==null){
            System.out.println("("+node.x+","+node.y+")");
        }else {
            print(node.pre);
            System.out.println("("+node.x+","+node.y+")");
        }
    }

    /**
     * 往四个方向寻找一个可以到达的点
     */
    private static Node find(Node node){
        if (maze[node.x+1][node.y]==0){
            //标记已经到达过
            maze[node.x+1][node.y]=2;
            return new Node(node.x+1, node.y, node);
        }
        if (maze[node.x-1][node.y]==0){
            maze[node.x-1][node.y]=2;
            return new Node(node.x-1, node.y, node);
        }
        if (maze[node.x][node.y+1]==0){
            maze[node.x][node.y+1]=2;
            return new Node(node.x, node.y+1, node);
        }
        if (maze[node.x][node.y-1]==0){
            maze[node.x][node.y-1]=2;
            return new Node(node.x, node.y-1, node);
        }
        return null;
    }

    static class Node{
        int x;
        int y;
        Node pre;

        public Node(int x, int y, Node pre) {
            this.x = x;
            this.y = y;
            this.pre = pre;
        }
    }

}

运行截图

在这里插入图片描述

记录点滴,乐于分享,转载请注明出处。

愿我们能以梦为马,不负人生韶华! 与君共勉!

  • 作者:金昊霖
  • 发表时间:2020-7-04
  • 版权声明:自由转载-非商用-非衍生-保留署名(创意共享3.0许可证)
  • 评论

    留言