Leetcode 499 Solution

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

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

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

            int dy[4] = {0, 0, -1, 1};
            int dx[4] = {-1, 1, 0, 0};
            char action_ch[4] = {'l', 'r', 'u', 'd'};

            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++;

                    if (i == hole[0] && j == hole[1])
                        break;
                }

                auto pt = make_pair(i, j);
                auto next_dist = dists[y][x] + step;
                string action = actions[y][x] + action_ch[t];

                if (dists[i][j] > next_dist)
                {
                    q.push(pt);
                    dists[i][j] = next_dist;
                    actions[i][j] = action;
                }
                else if (dists[i][j] == next_dist && action < actions[i][j])
                {
                    q.push(pt);
                    actions[i][j] = action;
                }
            }
        }

        if (dists[dest.first][dest.second] == INT_MAX)
            return "impossible";
        else
            return actions[dest.first][dest.second];
    }
};