LeetCode刷题实战490：迷宫-技术圈

LeetCode刷题实战490：迷宫

共 2479字，需浏览 5分钟

· 2022-01-09

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做迷宫，我们先来看题面：

https://leetcode-cn.com/problems/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.

由空地和墙组成的迷宫中有一个球。球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。

给定球的起始位置，目的地和迷宫，判断球能否在目的地停下。

迷宫由一个0和1的二维数组表示。1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。

示例

解题

https://blog.csdn.net/weixin_44171872/article/details/108931956

主要思路：

（1）广度优先搜索；

（2）将迷宫maze的元素置为2，来标识访问过的变换方向的位置；

（3）使用队列，存储各个可能变换方向的位置，并判断每个变换方向的位置是否是终点位置，若是，则返回true，否则，在没有访问过的情形下，压入到队列中；

class Solution {
public:
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        if(start==destination){
            return true;
        }
        //变换方向的位置使用2进行标识
        maze[start[0]][start[1]]=2;
        //使用队列实现广度优先搜索
        queue<vector<int>> q;
        //压入初始位置
        q.push(start);
        while(!q.empty()){//终止条件是没有可以判断的位置
          //取出当前需要判断的位置
            vector<int> tmp=q.front();
            q.pop();
            //起始位置
            //向上方向
            int row=tmp[0];
            int col=tmp[1];
            while(row>=0&&maze[row][col]!=1){//向上
                --row;
            }
            //判断终止位置是否是目的位置
            if(row+1==destination[0]&&col==destination[1]){
                return true;
            }
            //若当前终止位置之前没有访问过，则压入队列，并进行标识
            if(maze[row+1][col]!=2){
                q.push({row+1,col});
                maze[row+1][col]=2;
            }

      //向下方向
            row=tmp[0];
            while(row1){
                ++row;
            }
            if(row-1==destination[0]&&col==destination[1]){
                return true;
            }
            if(maze[row-1][col]!=2){
                q.push({row-1,col});
                maze[row-1][col]=2;
            }
      
      //向左方向
            row=tmp[0];
            while(col>=0&&maze[row][col]!=1){
                --col;
            }
            if(row==destination[0]&&col+1==destination[1]){
                return true;
            }
            if(maze[row][col+1]!=2){
                q.push({row,col+1});
                maze[row][col+1]=2;
            }
            //向右方向
            col=tmp[1];
            while(col0].size()&&maze[row][col]!=1){
                ++col;
            }
            if(row==destination[0]&&col-1==destination[1]){
                return true;
            }
            if(maze[row][col-1]!=2){
                q.push({row,col-1});
                maze[row][col-1]=2;
            }
        }
        return false;//跳出循环，说明没有找到合适的位置
    }
};