Description

Submission

class Solution {
    
public:
    int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        // bfs
        queue<pair<int,int>> q;
        int n = maze.size();
        int m = maze[0].size();

        vector<vector<int>> dp(n, vector<int>(m, INT_MAX / 2));

        q.push({start[0], start[1]});
        dp[start[0]][start[1]] = 0;
        vector<vector<int>> ds = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        while(!q.empty()) {
            auto p = q.front();
            q.pop();

            for(auto& d : ds) {
                // find the furthest
                int x = p.first, y = p.second;
                for(; x >= 0 && x < n && y >= 0 && y < m && !maze[x][y]; x += d[0], y += d[1]);
                x -= d[0], y -= d[1];

                int new_val = dp[p.first][p.second] + max(abs(x-p.first), abs(y-p.second));
                if(new_val < dp[x][y]) {
                    dp[x][y] = new_val;
                    q.push({x, y});
                }
            }
        }

        if(dp[destination[0]][destination[1]] == INT_MAX / 2) return -1;

        return dp[destination[0]][destination[1]];
    }
};