[leetcode/lintcode 题解] 阿里算法面试真题:迷宫

简介: [leetcode/lintcode 题解] 阿里算法面试真题:迷宫

描述
在迷宫中有一个球,里面有空的空间和墙壁。球可以通过滚上,下,左或右移动,
但它不会停止滚动直到撞到墙上。当球停止时,它可以选择下一个方向。
给定球的起始位置,目的地和迷宫,确定球是否可以停在终点。
迷宫由二维数组表示。1表示墙和0表示空的空间。你可以假设迷宫的边界都是墙。开始和目标坐标用行和列索引表示。

1.在迷宫中只有一个球和一个目的地。
2.球和目的地都存在于一个空的空间中,它们最初不会处于相同的位置。
3.给定的迷宫不包含边框(比如图片中的红色矩形),但是你可以假设迷宫的边界都是墙。
5.迷宫中至少有2个空的空间,迷宫的宽度和高度都不会超过100。

在线评测地址:领扣题库官网

样例1
输入:
map = 
[
 [0,0,1,0,0],
 [0,0,0,0,0],
 [0,0,0,1,0],
 [1,1,0,1,1],
 [0,0,0,0,0]
]
start = [0,4]
end = [3,2]
输出:
false
样例2
输入:
map = 
[[0,0,1,0,0],
 [0,0,0,0,0],
 [0,0,0,1,0],
 [1,1,0,1,1],
 [0,0,0,0,0]
]
start = [0,4]
end = [4,4]
输出:
true

算法:BFS
简单的BFS。由于没有其他要求,我们只需要在BFS的过程中在队列里记录当前的坐标即可。

  • 将地图的起点放入队列。
  • 进行广度优先搜索。

    • 每一次取出队首的元素,先判断是否到了终点,到了终点直接退出。
    • 若没有到达,往四周的方向滚,直到滚到墙为止。若到达的位置没有被访问,那么加入队列中。
  • 若整个过程都没有访问到终点,返回false即可。

上述也是一般BFS的执行过程。
复杂度分析

  • 时间复杂度O(n∗m)O(n∗m)
  • 有可能会遍历map上的每个点
  • 空间复杂度O(n∗m)
public class Solution {

    /**

     * @param maze: the maze

     * @param start: the start

     * @param destination: the destination

     * @return: whether the ball could stop at the destination

     */

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {

        // write your code here

        int n = maze.length;

        int m = maze[0].length;

        boolean[][] visited = new boolean[n][m];

        int[] dx = new int[]{0, -1, 0, 1};

        int[] dy = new int[]{1, 0, -1, 0};

        Queue<int[]> queue = new LinkedList<>();

        queue.offer(start);

        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {

            int[] cur = queue.poll();

            if (cur[0] == destination[0] && cur[1] == destination[1]) {

                return true;

            }

            for (int direction = 0; direction < 4; direction++) {

                int nx = cur[0], ny = cur[1];

                while (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == 0) {

                    nx += dx[direction];

                    ny += dy[direction];

                }

                nx -= dx[direction];

                ny -= dy[direction];

                if (!visited[nx][ny]) {

                    visited[nx][ny] = true;

                    queue.offer(new int[]{nx, ny});

                }

            }

        }

        return false;

    }

}

更多题解参考:九章官网solution

相关文章
|
1月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
2月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
2月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
37 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
2月前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
2月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
2月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
93 2
|
2月前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
54 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
63 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
128 2

热门文章

最新文章