LeetCode Solutions

			

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);
    }
  }
};

			

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");
    }
  }
}

			

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