Question

499. 迷宫 III

English Version

题目描述

由空地和墙组成的迷宫中有一个球。球可以向上（u）下（d）左（l）右（r）四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。迷宫中还有一个洞，当球运动经过洞时，就会掉进洞里。

给定球的起始位置，目的地和迷宫，找出让球以最短距离掉进洞里的路径。 距离的定义是球从起始位置（不包括）到目的地（包括）经过的空地个数。通过'u', 'd', 'l' 和 'r'输出球的移动方向。 由于可能有多条最短路径， 请输出字典序最小的路径。如果球无法进入洞，输出"impossible"。

迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。

 

示例1:

输入 1: 迷宫由以下二维数组表示

0 0 0 0 0
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 1 0 0 0

输入 2: 球的初始位置 (rowBall, colBall) = (4, 3)
输入 3: 洞的位置 (rowHole, colHole) = (0, 1)

输出: "lul"

解析: 有两条让球进洞的最短路径。
第一条路径是 左 -> 上 -> 左, 记为 "lul".
第二条路径是 上 -> 左, 记为 'ul'.
两条路径都具有最短距离6, 但'l' < 'u'，故第一条路径字典序更小。因此输出"lul"。

示例 2:

输入 1: 迷宫由以下二维数组表示

0 0 0 0 0
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 1 0 0 0

输入 2: 球的初始位置 (rowBall, colBall) = (4, 3)
输入 3: 洞的位置 (rowHole, colHole) = (3, 0)

输出: "impossible"

示例: 球无法到达洞。

 

注意:

1. 迷宫中只有一个球和一个目的地。
2. 球和洞都在空地上，且初始时它们不在同一位置。
3. 给定的迷宫不包括边界 (如图中的红色矩形), 但你可以假设迷宫的边缘都是墙壁。
4. 迷宫至少包括2块空地，行数和列数均不超过30。

解法

方法一：BFS

class Solution:
  def findShortestWay(
    self, maze: List[List[int]], ball: List[int], hole: List[int]
  ) -> str:
    m, n = len(maze), len(maze[0])
    r, c = ball
    rh, ch = hole
    q = deque([(r, c)])
    dist = [[inf] * n for _ in range(m)]
    dist[r][c] = 0
    path = [[None] * n for _ in range(m)]
    path[r][c] = ''
    while q:
      i, j = q.popleft()
      for a, b, d in [(-1, 0, 'u'), (1, 0, 'd'), (0, -1, 'l'), (0, 1, 'r')]:
        x, y, step = i, j, dist[i][j]
        while (
          0 <= x + a < m
          and 0 <= y + b < n
          and maze[x + a][y + b] == 0
          and (x != rh or y != ch)
        ):
          x, y = x + a, y + b
          step += 1
        if dist[x][y] > step or (
          dist[x][y] == step and path[i][j] + d < path[x][y]
        ):
          dist[x][y] = step
          path[x][y] = path[i][j] + d
          if x != rh or y != ch:
            q.append((x, y))
    return path[rh][ch] or 'impossible'

class Solution {
  public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
    int m = maze.length;
    int n = maze[0].length;
    int r = ball[0], c = ball[1];
    int rh = hole[0], ch = hole[1];
    Deque<int[]> q = new LinkedList<>();
    q.offer(new int[] {r, c});
    int[][] dist = new int[m][n];
    for (int i = 0; i < m; ++i) {
      Arrays.fill(dist[i], Integer.MAX_VALUE);
    }
    dist[r][c] = 0;
    String[][] path = new String[m][n];
    path[r][c] = "";
    int[][] dirs = {{-1, 0, 'u'}, {1, 0, 'd'}, {0, -1, 'l'}, {0, 1, 'r'}};
    while (!q.isEmpty()) {
      int[] p = q.poll();
      int i = p[0], j = p[1];
      for (int[] dir : dirs) {
        int a = dir[0], b = dir[1];
        String d = String.valueOf((char) (dir[2]));
        int x = i, y = j;
        int step = dist[i][j];
        while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0
          && (x != rh || y != ch)) {
          x += a;
          y += b;
          ++step;
        }
        if (dist[x][y] > step
          || (dist[x][y] == step && (path[i][j] + d).compareTo(path[x][y]) < 0)) {
          dist[x][y] = step;
          path[x][y] = path[i][j] + d;
          if (x != rh || y != ch) {
            q.offer(new int[] {x, y});
          }
        }
      }
    }
    return path[rh][ch] == null ? "impossible" : path[rh][ch];
  }
}

class Solution {
public:
  string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
    int m = maze.size();
    int n = maze[0].size();
    int r = ball[0], c = ball[1];
    int rh = hole[0], ch = hole[1];
    queue<pair<int, int>> q;
    q.push({r, c});
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
    dist[r][c] = 0;
    vector<vector<string>> path(m, vector<string>(n, ""));
    vector<vector<int>> dirs = {{-1, 0, 'u'}, {1, 0, 'd'}, {0, -1, 'l'}, {0, 1, 'r'}};
    while (!q.empty()) {
      auto p = q.front();
      q.pop();
      int i = p.first, j = p.second;
      for (auto& dir : dirs) {
        int a = dir[0], b = dir[1];
        char d = (char) dir[2];
        int x = i, y = j;
        int step = dist[i][j];
        while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0 && (x != rh || y != ch)) {
          x += a;
          y += b;
          ++step;
        }
        if (dist[x][y] > step || (dist[x][y] == step && (path[i][j] + d < path[x][y]))) {
          dist[x][y] = step;
          path[x][y] = path[i][j] + d;
          if (x != rh || y != ch) q.push({x, y});
        }
      }
    }
    return path[rh][ch] == "" ? "impossible" : path[rh][ch];
  }
};

import "math"

func findShortestWay(maze [][]int, ball []int, hole []int) string {
  m, n := len(maze), len(maze[0])
  r, c := ball[0], ball[1]
  rh, ch := hole[0], hole[1]
  q := [][]int{[]int{r, c}}
  dist := make([][]int, m)
  path := make([][]string, m)
  for i := range dist {
    dist[i] = make([]int, n)
    path[i] = make([]string, n)
    for j := range dist[i] {
      dist[i][j] = math.MaxInt32
      path[i][j] = ""
    }
  }
  dist[r][c] = 0
  dirs := map[string][]int{"u": {-1, 0}, "d": {1, 0}, "l": {0, -1}, "r": {0, 1}}
  for len(q) > 0 {
    p := q[0]
    q = q[1:]
    i, j := p[0], p[1]
    for d, dir := range dirs {
      a, b := dir[0], dir[1]
      x, y := i, j
      step := dist[i][j]
      for x+a >= 0 && x+a < m && y+b >= 0 && y+b < n && maze[x+a][y+b] == 0 && (x != rh || y != ch) {
        x += a
        y += b
        step++
      }
      if dist[x][y] > step || (dist[x][y] == step && (path[i][j]+d) < path[x][y]) {
        dist[x][y] = step
        path[x][y] = path[i][j] + d
        if x != rh || y != ch {
          q = append(q, []int{x, y})
        }
      }
    }
  }
  if path[rh][ch] == "" {
    return "impossible"
  }
  return path[rh][ch]
}