499. The Maze III (Hard)

There is aballin a maze with empty spaces and walls. The ball can go through empty spaces by rollingup(u),down(d),left(l) orright(r), but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction. There is also aholein this maze. The ball will drop into the hole if it rolls on to the hole.

Given theball position, thehole positionand themaze, find out how the ball could drop into the hole by moving theshortest distance. The distance is defined by the number ofempty spacestraveled by the ball from the start position (excluded) to the hole (included). Output the movingdirectionsby using 'u', 'd', 'l' and 'r'. Since there could be several different shortest ways, you should output thelexicographically smallestway. If the ball cannot reach the hole, output "impossible".

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The ball and the hole coordinates are represented by row and column indexes.
https://leetcode.com/problems/the-maze-iii/description/