[LeetCode] The Maze 迷宫

简介:

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball's start position, the destination and the maze, determine whether the ball could stop at the destination.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

Example 1

Input 1: a maze represented by a 2D array

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

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (4, 4)

Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

Example 2

Input 1: a maze represented by a 2D array

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

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (3, 2)

Output: false
Explanation: There is no way for the ball to stop at the destination.

Note:

  1. There is only one ball and one destination in the maze.
  2. Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
  3. The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
  4. The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.

 

这道题让我们遍历迷宫,但是与以往不同的是,这次迷宫是有一个滚动的小球,这样就不是每次只走一步了,而是朝某一个方向一直滚,直到遇到墙或者边缘才停下来,我记得貌似之前在手机上玩过类似的游戏。那么其实还是要用DFS或者BFS来解,只不过需要做一些修改。先来看DFS的解法,我们用DFS的同时最好能用上优化,即记录中间的结果,这样可以避免重复运算,提高效率。我们用二维数组dp来保存中间结果,然后用maze数组本身通过将0改为-1来记录某个点是否被访问过,这道题的难点是在于处理一直滚的情况,其实也不难,只要我们有了方向,只要一直在那个方向上往前走,每次判读是否越界了或者是否遇到墙了即可,然后对于新位置继续调用递归函数,参见代码如下:

解法一:

class Solution {
public:
    vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        if (maze.empty() || maze[0].empty()) return true;
        int m = maze.size(), n = maze[0].size();
        vector<vector<int>> dp(m, vector<int>(n, -1));
        return helper(maze, dp, start[0], start[1], destination[0], destination[1]);
    }
    bool helper(vector<vector<int>>& maze, vector<vector<int>>& dp, int i, int j, int di, int dj) {
        if (i == di && j == dj) return true;
        if (dp[i][j] != -1) return dp[i][j];
        bool res = false;
        int m = maze.size(), n = maze[0].size();
        maze[i][j] = -1;
        for (auto dir : dirs) {
            int x = i, y = j;
            while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] != 1) {
                x += dir[0]; y += dir[1];
            }
            x -= dir[0]; y -= dir[1];
            if (maze[x][y] != -1) {
                res |= helper(maze, dp, x, y, di, dj);
            }
        }
        dp[i][j] = res;
        return res;
    }
};

同样的道理,对于BFS的实现需要用到队列queue,在对于一直滚的处理跟上面相同,参见代码如下:

解法二:

class Solution {
public:
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        if (maze.empty() || maze[0].empty()) return true;
        int m = maze.size(), n = maze[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
        queue<pair<int, int>> q;
        q.push({start[0], start[1]});
        visited[start[0]][start[1]] = true;
        while (!q.empty()) {
            auto t = q.front(); q.pop();
            if (t.first == destination[0] && t.second == destination[1]) return true;
            for (auto dir : dirs) {
                int x = t.first, y = t.second;
                while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
                    x += dir[0]; y += dir[1];
                }
                x -= dir[0]; y -= dir[1];
                if (!visited[x][y]) {
                    visited[x][y] = true;
                    q.push({x, y});
                }
            }
        }
        return false;
    }
};

 本文转自博客园Grandyang的博客,原文链接:The Maze 迷宫,如需转载请自行联系原博主。

相关文章
|
6月前
|
机器学习/深度学习 存储
leetcode-1036:逃离大迷宫
leetcode-1036:逃离大迷宫
33 0
|
存储
Leetcode-每日一题1210. 穿过迷宫的最少移动次数(BFS)
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/weixin_46618592/article/details/128890280?spm=1001.2014.3001.5501
115 0
Leetcode-每日一题1210. 穿过迷宫的最少移动次数(BFS)
|
机器学习/深度学习
力扣-1036. 逃离大迷宫
在一个 106 x 106 的网格中,每个网格上方格的坐标为 (x, y) 。 现在从源方格 source = [sx, sy] 开始出发,意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表,其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。 每次移动,都可以走到网格中在四个方向上相邻的方格,只要该方格 不 在给出的封锁列表 blocked 上。同时,不允许走出网格。 只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则,返回 false。
99 0
力扣-1036. 逃离大迷宫
|
机器学习/深度学习 C++
【力扣·每日一题】1036. 逃离大迷宫 (C++ bfs 思维)
【力扣·每日一题】1036. 逃离大迷宫 (C++ bfs 思维)
96 0
【力扣·每日一题】1036. 逃离大迷宫 (C++ bfs 思维)
|
算法 定位技术 索引
[leetcode/lintcode 题解] 阿里算法面试真题:迷宫
[leetcode/lintcode 题解] 阿里算法面试真题:迷宫
[leetcode/lintcode 题解] 阿里算法面试真题:迷宫
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
55 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
113 2