LeetCode刷题实战505：迷宫II

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

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

https://leetcode-cn.com/problems/the-maze-ii/

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, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.

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.

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

给定球的起始位置，目的地和迷宫，找出让球停在目的地的最短距离。距离的定义是球从起始位置（不包括）到目的地（包括）经过的空地个数。如果球无法停在目的地，返回 -1。

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

示例

解题

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

主要思路：使用广度优先，和迷宫1的思路基本一致，区别只是另外加一个数组来记录之前出现过的转向位置处的步距，来保证获得最小的步距

class Solution {
public:
    int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        if(start==destination){
            return 0;
        }
        //变换方向的位置使用2进行标识
        maze[start[0]][start[1]]=2;
        //使用队列实现广度优先搜索
        queue<vector<int>> q;
        //压入初始位置
        q.push({start[0],start[1]});
        //保存出现过的步距，保证能够获得最小的步距
        vector<vector<int>> dis(maze.size(),vector<int>(maze[0].size(),INT_MAX));
        dis[start[0]][start[1]]=0;
        while(!q.empty()){//终止条件是没有可以判断的位置
          //取出当前需要判断的位置
            vector<int> tmp=q.front();
            q.pop();
            //起始位置
            //向上方向
            int row=tmp[0];
            int col=tmp[1];
            int len=dis[row][col];
            while(row>=0&&maze[row][col]!=1){//向上
                --row;
            }
            //若当前终止位置之前没有访问过，或者可以获得更小的步距，则压入队列，并进行标识
            if(maze[row+1][col]!=2||(dis[row+1][col]>len+tmp[0]-(row+1))){
                dis[row+1][col]=len+tmp[0]-(row+1);
                q.push({row+1,col});
                maze[row+1][col]=2;
            }

      //向下方向
            row=tmp[0];
            while(row<maze.size()&&maze[row][col]!=1){
                ++row;
            }

            if(maze[row-1][col]!=2||(dis[row-1][col]>len+row-1-tmp[0])){
                dis[row-1][col]=len+row-1-tmp[0];
                q.push({row-1,col});
                maze[row-1][col]=2;
            }
      
      //向左方向
            row=tmp[0];
            while(col>=0&&maze[row][col]!=1){
                --col;
            }

            if(maze[row][col+1]!=2||(dis[row][col+1]>len+tmp[1]-(col+1))){
                dis[row][col+1]=len+tmp[1]-(col+1);
                q.push({row,col+1});
                maze[row][col+1]=2;
            }
            //向右方向
            col=tmp[1];
            while(col<maze[0].size()&&maze[row][col]!=1){
                ++col;
            }

            if(maze[row][col-1]!=2||(dis[row][col-1]>len+col-1-tmp[1])){
                dis[row][col-1]=len+col-1-tmp[1];
                q.push({row,col-1});
                maze[row][col-1]=2;
            }
        }
        return dis[destination[0]][destination[1]]==INT_MAX?-1:dis[destination[0]][destination[1]];//跳出循环，说明没有找到合适的位置
    }
};