Algorithm (Shortest Path)

1. Convert the maze into a weighted graph and run any single source shortest path algorithm to get the desired result.
2. In our implementation, we chose Dijkstra. We used the implicit graph instead of constructing the graph explicitly for efficiency.

Time Complexity

1. Let $N=\max(\texttt{row(maze)},\texttt{col(maze)}).$ There are in total of $O(N^{2})$ vertices and each vertices has at most 4 edges.
2. Thus in total the complexity is $O((N^{2}+4N^{2})\cdot\log(N^{2}))=O\left(N^{2}\log N\right).$

Memory

1. $O(N^{2})$ for all the helper variables (see code).

Code

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts) const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts) { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F>
recursive(F)->recursive<F>;
auto const rec = [](auto f) { return recursive{std::move(f)}; };

class Solution {
 public:
  string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
    struct direction_t {
      int dr;
      int dc;
      string as_string;
    };

    struct node_t {
      int r;
      int c;
      int dist;
      string move;
    };

    const auto dirs = array<direction_t, 4>{direction_t{0, 1, "r"},
                                            direction_t{0, -1, "l"},
                                            direction_t{1, 0, "d"},
                                            direction_t{-1, 0, "u"}};

    const auto R = size(maze), C = size(maze[0]);

    auto node_comp = [](const node_t& x, const node_t& y) {
      if (x.dist == y.dist)
        return x.move > y.move;
      else
        return x.dist > y.dist;
    };

    auto check_bound = [&](int r, int c) {
      return (r >= 0 and r < R and c >= 0 and c < C and maze[r][c] == 0);
    };

    auto walk = rec([&](auto&& walk, const node_t node, const direction_t& dir) {
      const auto [dr, dc, as_string] = dir;
      const auto [r, c, dist, move]  = node;
      if (r == hole[0] and c == hole[1])
        return node_t{r, c, dist, move + as_string};
      else if (not check_bound(r + dr, c + dc))
        return node_t{r, c, dist, move + as_string};
      else
        return walk(node_t{r + dr, c + dc, dist + 1, move}, dir);
    });

    auto solution = [&]() -> string {
      auto pq    = priority_queue<node_t, vector<node_t>, decltype(node_comp)>(node_comp);
      auto dist  = vector<vector<int>>(R, vector<int>(C, INT_MAX));
      auto path  = vector<vector<string>>(R, vector<string>(C, string()));

      auto relax = [&](const node_t& new_node)  {
        if (new_node.dist < dist[new_node.r][new_node.c]
            or (new_node.dist == dist[new_node.r][new_node.c] and new_node.move < path[new_node.r][new_node.c])) {
          dist[new_node.r][new_node.c] = new_node.dist;
          path[new_node.r][new_node.c] = new_node.move;
          pq.push(new_node);
        }
      };

      for ((pq.push(node_t{ball[0], ball[1], 0, string()}), dist[ball[0]][ball[1]] = 0); not empty(pq);) {
        const auto cur_node = pq.top();
        pq.pop();
        if (cur_node.r == hole[0] and cur_node.c == hole[1])
          return cur_node.move;
        for (const auto& d : dirs)
          relax(walk(cur_node, d));
      }
      return "impossible";
    };
    return solution();
  }
};