Skip to content

499. The Maze III 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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 zeros 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 because maze[i][j] == 0 || 1.
      if (dx == 0)
        dfs(maze, i, j, hole, 1, 0, steps, std::move(minSteps), path + "d",
            ans);
      if (dy == 0)
        dfs(maze, i, j, hole, 0, -1, steps, std::move(minSteps), path + "l",
            ans);
      if (dy == 0)
        dfs(maze, i, j, hole, 0, 1, steps, std::move(minSteps), path + "r",
            ans);
      if (dx == 0)
        dfs(maze, i, j, hole, -1, 0, steps, std::move(minSteps), path + "u",
            ans);
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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 zeros 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 because 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");
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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 zeros 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 because 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