Question

490. 迷宫

English Version

题目描述

由空地（用 0 表示）和墙（用 1 表示）组成的迷宫 maze 中有一个球。球可以途经空地向 上、下、左、右 四个方向滚动，且在遇到墙壁前不会停止滚动。当球停下时，可以选择向下一个方向滚动。

给你一个大小为 m x n 的迷宫 maze ，以及球的初始位置 start 和目的地 destination ，其中 start = [startrow, startcol] 且 destination = [destinationrow, destinationcol] 。请你判断球能否在目的地停下：如果可以，返回 true ；否则，返回 false 。

你可以 假定迷宫的边缘都是墙壁（参考示例）。

 

示例 1：

输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
输出：true
解释：一种可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。

示例 2：

输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
输出：false
解释：不存在能够使球停在目的地的路径。注意，球可以经过目的地，但无法在那里停驻。

示例 3：

输入：maze = [[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]], start = [4,3], destination = [0,1]
输出：false

 

提示：

• m == maze.length
• n == maze[i].length
• 1 <= m, n <= 100
• maze[i][j] is 0 or 1.
• start.length == 2
• destination.length == 2
• 0 <= startrow, destinationrow <= m
• 0 <= startcol, destinationcol <= n
• 球和目的地都在空地上，且初始时它们不在同一位置
• 迷宫 至少包括 2 块空地

解法

方法一

class Solution:
  def hasPath(
    self, maze: List[List[int]], start: List[int], destination: List[int]
  ) -> bool:
    def dfs(i, j):
      if vis[i][j]:
        return
      vis[i][j] = True
      if [i, j] == destination:
        return
      for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
        x, y = i, j
        while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0:
          x, y = x + a, y + b
        dfs(x, y)

    m, n = len(maze), len(maze[0])
    vis = [[False] * n for _ in range(m)]
    dfs(start[0], start[1])
    return vis[destination[0]][destination[1]]

class Solution {
  private boolean[][] vis;
  private int[][] maze;
  private int[] d;
  private int m;
  private int n;

  public boolean hasPath(int[][] maze, int[] start, int[] destination) {
    m = maze.length;
    n = maze[0].length;
    d = destination;
    this.maze = maze;
    vis = new boolean[m][n];
    dfs(start[0], start[1]);
    return vis[d[0]][d[1]];
  }

  private void dfs(int i, int j) {
    if (vis[i][j]) {
      return;
    }
    vis[i][j] = true;
    if (i == d[0] && j == d[1]) {
      return;
    }
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i, y = j;
      int a = dirs[k], b = dirs[k + 1];
      while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0) {
        x += a;
        y += b;
      }
      dfs(x, y);
    }
  }
}

class Solution {
public:
  vector<vector<int>> maze;
  vector<vector<bool>> vis;
  vector<int> d;
  int m;
  int n;

  bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
    m = maze.size();
    n = maze[0].size();
    d = destination;
    vis.resize(m, vector<bool>(n, false));
    this->maze = maze;
    dfs(start[0], start[1]);
    return vis[d[0]][d[1]];
  }

  void dfs(int i, int j) {
    if (vis[i][j]) return;
    vis[i][j] = true;
    if (i == d[0] && j == d[1]) return;
    vector<int> dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i, y = j;
      int a = dirs[k], b = dirs[k + 1];
      while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0) {
        x += a;
        y += b;
      }
      dfs(x, y);
    }
  }
};

func hasPath(maze [][]int, start []int, destination []int) bool {
  m, n := len(maze), len(maze[0])
  vis := make([][]bool, m)
  for i := range vis {
    vis[i] = make([]bool, n)
  }
  var dfs func(i, j int)
  dfs = func(i, j int) {
    if vis[i][j] {
      return
    }
    vis[i][j] = true
    if i == destination[0] && j == destination[1] {
      return
    }
    dirs := []int{-1, 0, 1, 0, -1}
    for k := 0; k < 4; k++ {
      x, y := i, j
      a, b := dirs[k], dirs[k+1]
      for x+a >= 0 && x+a < m && y+b >= 0 && y+b < n && maze[x+a][y+b] == 0 {
        x += a
        y += b
      }
      dfs(x, y)
    }
  }
  dfs(start[0], start[1])
  return vis[destination[0]][destination[1]]
}

方法二

class Solution:
  def hasPath(
    self, maze: List[List[int]], start: List[int], destination: List[int]
  ) -> bool:
    m, n = len(maze), len(maze[0])
    q = deque([start])
    rs, cs = start
    vis = {(rs, cs)}
    while q:
      i, j = q.popleft()
      for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
        x, y = i, j
        while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0:
          x, y = x + a, y + b
        if [x, y] == destination:
          return True
        if (x, y) not in vis:
          vis.add((x, y))
          q.append((x, y))
    return False

class Solution {
  public boolean hasPath(int[][] maze, int[] start, int[] destination) {
    int m = maze.length;
    int n = maze[0].length;
    boolean[][] vis = new boolean[m][n];
    vis[start[0]][start[1]] = true;
    Deque<int[]> q = new LinkedList<>();
    q.offer(start);
    int[] dirs = {-1, 0, 1, 0, -1};
    while (!q.isEmpty()) {
      int[] p = q.poll();
      int i = p[0], j = p[1];
      for (int k = 0; k < 4; ++k) {
        int x = i, y = j;
        int a = dirs[k], b = dirs[k + 1];
        while (
          x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0) {
          x += a;
          y += b;
        }
        if (x == destination[0] && y == destination[1]) {
          return true;
        }
        if (!vis[x][y]) {
          vis[x][y] = true;
          q.offer(new int[] {x, y});
        }
      }
    }
    return false;
  }
}

class Solution {
public:
  bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
    int m = maze.size();
    int n = maze[0].size();
    queue<vector<int>> q{{start}};
    vector<vector<bool>> vis(m, vector<bool>(n));
    vis[start[0]][start[1]] = true;
    vector<int> dirs = {-1, 0, 1, 0, -1};
    while (!q.empty()) {
      auto p = q.front();
      q.pop();
      int i = p[0], j = p[1];
      for (int k = 0; k < 4; ++k) {
        int x = i, y = j;
        int a = dirs[k], b = dirs[k + 1];
        while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0) {
          x += a;
          y += b;
        }
        if (x == destination[0] && y == destination[1]) return 1;
        if (!vis[x][y]) {
          vis[x][y] = true;
          q.push({x, y});
        }
      }
    }
    return 0;
  }
};

func hasPath(maze [][]int, start []int, destination []int) bool {
  m, n := len(maze), len(maze[0])
  vis := make([][]bool, m)
  for i := range vis {
    vis[i] = make([]bool, n)
  }
  vis[start[0]][start[1]] = true
  q := [][]int{start}
  dirs := []int{-1, 0, 1, 0, -1}
  for len(q) > 0 {
    i, j := q[0][0], q[0][1]
    q = q[1:]
    for k := 0; k < 4; k++ {
      x, y := i, j
      a, b := dirs[k], dirs[k+1]
      for x+a >= 0 && x+a < m && y+b >= 0 && y+b < n && maze[x+a][y+b] == 0 {
        x += a
        y += b
      }
      if x == destination[0] && y == destination[1] {
        return true
      }
      if !vis[x][y] {
        vis[x][y] = true
        q = append(q, []int{x, y})
      }
    }
  }
  return false
}