Leetcode 505 Solution

class Solution {
public:
    int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int m = maze.size();
        int n = maze[0].size();
        vector<vector<int>> dists(m, vector<int>(n, INT_MAX));

        queue<pair<int, int>> q;
        dists[start[0]][start[1]] = 0;
        q.push(make_pair(start[0], start[1]));

        auto dest = make_pair(destination[0], destination[1]);
        while (q.empty() == false)
        {
            auto pt = q.front();
            auto y = pt.first;
            auto x = pt.second;
            q.pop();

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

            for (int t = 0; t < 4; t++)
            {
                int i = y;
                int j = x;

                int step = 0;
                while (i + dy[t] >= 0 && i + dy[t] < m && j + dx[t] >= 0 && j + dx[t] < n && maze[i + dy[t]][j + dx[t]] == 0)
                {
                    i += dy[t];
                    j += dx[t];
                    step++;
                }

                auto pt = make_pair(i, j);
                auto next_dist = dists[y][x] + step;

                if (dists[i][j] > next_dist)
                {
                    q.push(pt);
                    dists[i][j] = next_dist;
                }
            }
        }

        return dists[dest.first][dest.second] == INT_MAX ? -1 : dists[dest.first][dest.second];
    }
};