• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball,
vector<int>& hole) {
string ans = "impossible";
dfs(maze, ball[0], ball[1], hole, 0, 0, 0, INT_MAX, "", ans);
return ans;
}

private:
void dfs(vector<vector<int>>& maze, int i, int j, const vector<int>& hole,
int dx, int dy, int steps, int&& minSteps, string&& path,
string& ans) {
if (steps >= minSteps)
return;

if (dx != 0 || dy != 0) {  // both are zero for the initial ball position
while (i + dx >= 0 && i + dx < maze.size() && j + dy >= 0 &&
j + dy < maze[0].size() && maze[i + dx][j + dy] != 1) {
i += dx;
j += dy;
++steps;
if (i == hole[0] && j == hole[1] && steps < minSteps) {
minSteps = steps;
ans = path;
}
}
}

if (maze[i][j] == 0 || steps + 2 < maze[i][j]) {
maze[i][j] = steps + 2;  // +2 to because of maze[i][j] == 0 || 1
if (dx == 0)
dfs(maze, i, j, hole, 1, 0, steps, move(minSteps), path + "d", ans);
if (dy == 0)
dfs(maze, i, j, hole, 0, -1, steps, move(minSteps), path + "l", ans);
if (dy == 0)
dfs(maze, i, j, hole, 0, 1, steps, move(minSteps), path + "r", ans);
if (dx == 0)
dfs(maze, i, j, hole, -1, 0, steps, move(minSteps), path + "u", ans);
}
}
};
``````

## JAVA

``````class Solution {
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
dfs(maze, ball[0], ball[1], hole, 0, 0, 0, "");
return ans;
}

private String ans = "impossible";
private int minSteps = Integer.MAX_VALUE;

private void dfs(int[][] maze, int i, int j, int[] hole, int dx, int dy, int steps,
final String path) {
if (steps >= minSteps)
return;

if (dx != 0 || dy != 0) { // both are zero for the initial ball position
while (i + dx >= 0 && i + dx < maze.length && j + dy >= 0 && j + dy < maze[0].length &&
maze[i + dx][j + dy] != 1) {
i += dx;
j += dy;
++steps;
if (i == hole[0] && j == hole[1] && steps < minSteps) {
minSteps = steps;
ans = path;
}
}
}

if (maze[i][j] == 0 || steps + 2 < maze[i][j]) {
maze[i][j] = steps + 2; // +2 to because of maze[i][j] == 0 || 1
if (dx == 0)
dfs(maze, i, j, hole, 1, 0, steps, path + "d");
if (dy == 0)
dfs(maze, i, j, hole, 0, -1, steps, path + "l");
if (dy == 0)
dfs(maze, i, j, hole, 0, 1, steps, path + "r");
if (dx == 0)
dfs(maze, i, j, hole, -1, 0, steps, path + "u");
}
}
}
``````

## Python

``````class Solution:
def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
ans = "impossible"
minSteps = math.inf

def dfs(i: int, j: int, dx: int, dy: int, steps: int, path: str):
nonlocal ans
nonlocal minSteps
if steps >= minSteps:
return

if dx != 0 or dy != 0:  # both are zero for the initial ball position
while 0 <= i + dx < len(maze) and 0 <= j + dy < len(maze[0]) \
and maze[i + dx][j + dy] != 1:
i += dx
j += dy
steps += 1
if i == hole[0] and j == hole[1] and steps < minSteps:
minSteps = steps
ans = path

if maze[i][j] == 0 or steps + 2 < maze[i][j]:
maze[i][j] = steps + 2  # +2 to because of maze[i][j] == 0 || 1
if dx == 0:
dfs(i, j, 1, 0, steps, path + 'd')
if dy == 0:
dfs(i, j, 0, -1, steps, path + 'l')
if dy == 0:
dfs(i, j, 0, 1, steps, path + 'r')
if dx == 0:
dfs(i, j, -1, 0, steps, path + 'u')

dfs(ball[0], ball[1], 0, 0, 0, '')
return ans
``````