【编程马拉松】【015-走迷宫】_Wang-Junchao的博客-程序员资料_马拉松迷宫

技术标签: 算法  数据  java  编程马拉松  游戏  

【编程马拉松算法目录】


【015-走迷宫】【工程下载>>>】


1 题目描述


  NowCoder最喜欢游乐场的迷宫游戏,他和小伙伴们比赛谁先走出迷宫。
  现在把迷宫的地图给你,你能帮他算出最快走出迷宫需要多少步吗?

1.1 输入描述:


  输入包含多组数据。
  每组数据包含一个10*10,由“#”和“.”组成的迷宫。其中“#”代表墙;“.”代表通路。
  入口在第一行第二列;出口在最后一行第九列。
  从任意一个“.”点都能一步走到上下左右四个方向的“.”点。

1.2 输出描述:


  对应每组数据,输出从入口到出口最短需要几步。

1.3 输入例子:


#.########
#........#
#........#
#........#
#........#
#........#
#........#
#........#
#........#
########.#

#.########
#........#
########.#
#........#
#.########
#........#
########.#
#........#
#.######.#
########.#

1.4 输出例子:


16
30

2 解题思路


  因为题意是使用最少的步数走出迷宫,所要可以使用广度优先遍历的方式,每处理完一层说明走了一步,最先到达出口使用的步数最少。根据输入的例子,迷宫的走法如图1所示。
这里写图片描述
图1 迷宫找最短路径

3 算法实现


import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

/**
 * Author: 王俊超
 * Time: 2016-05-11 18:59
 * CSDN: http://blog.csdn.net/derrantcm
 * Github: https://github.com/Wang-Jun-Chao
 * Declaration: All Rights Reserved !!!
 */
public class Main {
    
    private final static int N = 10;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
//        Scanner scanner = new Scanner(Main.class.getClassLoader().getResourceAsStream("data.txt"));

        while (scanner.hasNextLine()) {
            char[][] maze = new char[N][N];
            for (int i = 0; i < N; i++) {
                maze[i] = scanner.nextLine().toCharArray();
            }

            System.out.println(minStep(maze));
        }

        scanner.close();
    }

    /**
     * 求使用最少的步骤走出迷宫,迷宫大小固定为10*10,起点为(0, 1),终点为(9, 8)
     *
     * @param maze 迷宫
     * @return 走出迷宫最少的步数,走不出去返回-1
     */
    private static int minStep(char[][] maze) {

        // 记录当前处理层的位置
        Queue<Integer> curr = new ArrayDeque<>(N * N);
        // 记录下一层处理的位置
        Queue<Integer> next = new ArrayDeque<>(N * N);

        // 可以移动的四个方向,两个一组
        int[] d = {
   1, 0, 0, 1, -1, 0, 0, -1};

        // 添加起点;
        curr.add(0);
        curr.add(1);
        int x;
        int y;
        // 记录最少的步数
        int step = 0;

        while (!curr.isEmpty()) {
            x = curr.remove();
            y = curr.remove();

            // 找到终点位置
            if (x == 9 && y == 8) {
                return step;
            }

            // 处理(x, y)位置的四个方向
            for (int i = 0; i < d.length; i += 2) {
                int t = x + d[i];
                int v = y + d[i + 1];
                if (t >= 0 && t < N && v >= 0 && v < N && maze[t][v] == '.') {
                    // 标记已经访问过
                    maze[t][v] = '#';
                    // 访问的位置添加到队列中
                    next.add(t);
                    next.add(v);
                }
            }

            // 当前层已经处理完
            if (curr.isEmpty()) {
                // 步数加一
                step++;
                // 处理下一层
                Queue<Integer> temp = curr;
                curr = next;
                next = temp;
            }

        }

        // 执行到此说明找不到出路
        return -1;
    }
}

4 测试结果


5 其它信息


因为markddow不好编辑,因此将文档的图片上传以供阅读。Pdf和Word文档可以在Github上进行【下载>>>】

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/DERRANTCM/article/details/51700045

智能推荐

select count(0) from 和 select count(*) from 的区别_热带鱼2020的博客-程序员资料

select count(*) :查询总行数,并且会对表的每个字段进行扫描select count(0) :忽略所有列,只进行全表总行数

100天精通Python(基础篇)——第1天:Python和Vscode环境安装_无 羡ღ的博客-程序员资料

Python安装官网:http://www.python.org/download/安装成功后,打开命令提示符窗口(win+R,在输入cmd回车),敲入python后pip升级命令:python -m pip install --upgrade pippip install name //这里的name是要安装的第三方库名pip install name -i http://mirrors.aliyun.com/pypi/simple/ 国内镜像源阿里云:http://mirror

脑与认知科学3 脑神经影像下_一个不愿透露姓名的孩子的博客-程序员资料

脑与认知科学3 脑神经影像下Diffusion MRIfunctional MRItask-fMRIrs-fMRI这一讲继续介绍脑神经影像的常用方法。上一讲提到了MRI,这一讲介绍MRI更细致的一些应用。Diffusion MRIDiffusion MRI同样是利用MRI的机器,但在扫描的时候我们要试图扫描水分子的运动。因为自由的水分子与位于神经元中的水分子运动行为会有很大差别,自由水分子在三维空间中几乎是处于自由扩散(free diffusion)状态的;而神经纤维中的水分子只能按纤维的走向扩散。

Anglular8的@ViewChild的变化_春风又一季的博客-程序员资料

配置ViewChild / ContentChild查询的时间使用此功能时,必须提供静态标志以定义何时需要解析ViewChild和ContentChild实例。使用此功能时,必须提供静态标志以定义何时需要解析ViewChild和ContentChild实例。// Ensure Change Detection runs before accessing the [email protected]

思杰服务器需要显卡性能,【长期更新】Citrix日常问题支持以及各类KB大全_闫沐喜的博客-程序员资料

本文章页面收集的是关于Citrix一些常见问题KB以及一些问题处理的连接!2020年06月16更新产品生命周期Citrix软件技术支持服务周期,参考以下链接的内容:https://hfly.cc/70XH0v最近软件更新服务器虚拟化平台Citrix 服务器虚拟化硬件兼容性列表兼容性列表地址:https://hfly.cc/JezfACitrix 服务器虚拟化驱动版本 Citrix Hypervi...

Push failed fatal: unable to access ‘https://github.The requested URL returned error: 403_sunrj_go的博客-程序员资料

**Push failed fatal: unable to access 'https://github.The requested URL returned error: 403**Github 禁用了TLS v1.0 and v1.1,必须更新Windows的git凭证管理器,才行。https://github.com/Microsoft/Git-Credential-Manager-for-Windows/releases/tag/v1.14.0点击下载安装 GCMW-1.14.0.exe

随便推点

vue 2.0与vue 3.0中的本地文件下载_王王王晓晓蓉的博客-程序员资料_vue2.0js文件下载

需求:获取静态资源文件export.pdf,将pdf文档下载至本地方案:利用axios请求,get请求用blob流的方式下载项目1:vue 2.0 + element ui+es5中利用a标签,给个点击事件download()&lt;a id="attname" class="attname" href="javascript:void(0);" @click="download"&gt;帮助文档&lt;/a&gt;页面已经引用过axios,使用如下:import axios from 'ax

Gmail对比Outlook哪个更好_China_Ajax的博客-程序员资料_hotmail

随着 Slack、WhatsApp&nbsp;和&nbsp;Skype&nbsp;等实时通信应用程序的普及,您可能会惊讶地发现电子邮件仍然是工作中的主要通信工具 - 并且在全球拥有 39 亿用户,这种情况不太可能随时改变很快。主导该领域的是&nbsp;Gmail&nbsp;和&nbsp;Outlook——这两个世界上最受欢迎的电子邮件提供商。尽管两者之间有很多相似之处,但 Microsoft&nbsp;Outlook&nbsp;更像是一个电子邮件客户端,而&nbsp;Gmail&nbsp;本质上是网络邮

@Value获取不到值_zzy_阳阳的博客-程序员资料

@Value有两种获取application.properties值得方法: 一、PlaceHolder方式:格式${...}@Componentpublic class GetValue { @Value("${book.name}") private String name; public String getName() { return name

恢复报错ora-01180_kuaile_yuanzi的博客-程序员资料_ora-01180

https://blog.csdn.net/weixin_34029949/article/details/85997154最近在验证、测试备份有效性时,遇到了“ORA-01180: can not create datafile 1”这个错误,顺便结合metalink的官方文档“RMAN restore fails with ORA-01180: can not create datafile...

知名互联网公司校招中常见的算法题_dengya2093的博客-程序员资料

本次Chat,主要从知名互联网公司在面试中喜欢提问的算法入手,给大家详细阐述讲解面试中的高频率算法题。涉及到的算法题主要包括:排序和查找、链表、二叉树、队列、堆栈、字符串以及数组等方面。如果你想在来年的校园招聘中拿下一线互联网的Offer,那么本次Chat将助你玩转算法面试~面试,是大家从学校走向社会的第一步。大型互联网公司的校园招聘,从形式上说,面试一般分为2-3轮技术面试+1轮H...

java中用jedis报错_使用Jedis在高并发报错 (java.net.SocketException: Connection reset by peer: socket write error)..._袁均林的博客-程序员资料

使用Jedis在高并发报错 (java.net.SocketException: Connection reset by peer: socket write error)1.报错信息java.lang.reflect.InvocationTargetException: nullat sun.reflect.GeneratedMethodAccessor15.invoke(Unknown Sou...

推荐文章

热门文章

相关标签