The Maze II.cpp

class Solution {
public:
    int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int m = maze.size(), n = m? maze[0].size(): 0, to = destination[0] * n + destination[1], from = start[0] * n + start[1];
        if(!m || !n)return -1;
        unordered_set<int> visited;
        vector<pair<int, int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        auto comp = [](const pair<int, int>& p1, const pair<int, int>& p2){ return p1.first > p2.first; };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> pq(comp);
        pq.push({0, from});
        while(pq.size())
        {
            auto p = pq.top();
            pq.pop();
            if(visited.find(p.second) != visited.end())
                continue;
            if(to == p.second)
                return p.first;
            visited.insert(p.second);
            int i = p.second / n, j = p.second % n;
            for(auto& dir : dirs)
            {
                int x = i, y = j, dist = p.first;
                while(x >= 0 && x < m && y >= 0 && y < n && !maze[x][y])
                {
                    x += dir.first;
                    y += dir.second;
                    ++dist;
                }
                x -= dir.first;
                y -= dir.second;
                --dist;
                pq.push({dist, x * n + y});
            }
        }
        return -1;
    }
};