499

class Solution {
public:
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
        vector<vector<string>> path(m, vector<string>(n));

        // distance of starting point is 0
        dis[ball[0]][ball[1]] = 0;
        queue<vector<int>> q;
        q.push(ball);

       // the order of ball move direction is lexicographically smallest, i.e. dlru
        vector<int> d1({1, 0, 0, -1}), d2({0, -1, 1, 0});
        string dirs = "dlru";

        while(!q.empty()) {
            int row = q.front()[0], col = q.front()[1];
            q.pop();
            for(int i = 0; i < 4; ++i) {
                int r = row+d1[i], c = col+d2[i], len = 0;
                while(r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0) {
                    r += d1[i];
                    c += d2[i];
                    len++;
                }
                r -= d1[i];
                c -= d2[i];

                // if the current move goes across the hole
                if((hole[0]-row)*(hole[0]-r) <= 0 && (hole[1]-col)*(hole[1]-c) <= 0) {
                    int k = abs(hole[0]-row)+abs(hole[1]-col);
                    if(dis[hole[0]][hole[1]] > dis[row][col]+k || (dis[hole[0]][hole[1]] == dis[row][col]+k && path[hole[0]][hole[1]] > path[row][col]+dirs[i])) {
                        dis[hole[0]][hole[1]] = dis[row][col]+k;
                        path[hole[0]][hole[1]] = path[row][col]+dirs[i];
                    }
                    continue;
                }

                // check whether the end point should be a new starting point
                if (dis[r][c] > dis[row][col]+len || (dis[r][c] == dis[row][col]+len && path[r][c] > path[row][col]+dirs[i])) {
                    dis[r][c] = dis[row][col]+len;
                    path[r][c] = path[row][col]+dirs[i];
                    q.push({r, c});
                }
            }
        }
        return path[hole[0]][hole[1]] == "" ? "impossible" : path[hole[0]][hole[1]];
    }
};