Question

1036. 逃离大迷宫

English Version

题目描述

在一个 10⁶ x 10⁶ 的网格中，每个网格上方格的坐标为 (x, y) 。

现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。

每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 blocked 上。同时，不允许走出网格。

只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。

 

示例 1：

输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。
无法向北或者向东移动是因为方格禁止通行。
无法向南或者向西移动是因为不能走出网格。

示例 2：

输入：blocked = [], source = [0,0], target = [999999,999999]
输出：true
解释：
因为没有方格被封锁，所以一定可以到达目标方格。

 

提示：

• 0 <= blocked.length <= 200
• blocked[i].length == 2
• 0 <= xi, yi < 106
• source.length == target.length == 2
• 0 <= sx, sy, tx, ty < 106
• source != target
• 题目数据保证 source 和 target 不在封锁列表内

解法

方法一

class Solution:
  def isEscapePossible(
    self, blocked: List[List[int]], source: List[int], target: List[int]
  ) -> bool:
    def dfs(source, target, seen):
      x, y = source
      if (
        not (0 <= x < 10**6 and 0 <= y < 10**6)
        or (x, y) in blocked
        or (x, y) in seen
      ):
        return False
      seen.add((x, y))
      if len(seen) > 20000 or source == target:
        return True
      for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
        next = [x + a, y + b]
        if dfs(next, target, seen):
          return True
      return False

    blocked = set((x, y) for x, y in blocked)
    return dfs(source, target, set()) and dfs(target, source, set())

class Solution {
  private int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  private static final int N = (int) 1e6;
  private Set<Integer> blocked;

  public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
    this.blocked = new HashSet<>();
    for (int[] b : blocked) {
      this.blocked.add(b[0] * N + b[1]);
    }
    return dfs(source, target, new HashSet<>()) && dfs(target, source, new HashSet<>());
  }

  private boolean dfs(int[] source, int[] target, Set<Integer> seen) {
    int sx = source[0], sy = source[1];
    int tx = target[0], ty = target[1];
    if (sx < 0 || sx >= N || sy < 0 || sy >= N || tx < 0 || tx >= N || ty < 0 || ty >= N
      || blocked.contains(sx * N + sy) || seen.contains(sx * N + sy)) {
      return false;
    }
    seen.add(sx * N + sy);
    if (seen.size() > 20000 || (sx == target[0] && sy == target[1])) {
      return true;
    }
    for (int[] dir : dirs) {
      if (dfs(new int[] {sx + dir[0], sy + dir[1]}, target, seen)) {
        return true;
      }
    }
    return false;
  }
}

typedef unsigned long long ULL;

class Solution {
public:
  vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  unordered_set<ULL> blocked;
  int N = 1e6;

  bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
    this->blocked.clear();
    for (auto& b : blocked) this->blocked.insert((ULL) b[0] * N + b[1]);
    unordered_set<ULL> s1;
    unordered_set<ULL> s2;
    return dfs(source, target, s1) && dfs(target, source, s2);
  }

  bool dfs(vector<int>& source, vector<int>& target, unordered_set<ULL>& seen) {
    int sx = source[0], sy = source[1];
    int tx = target[0], ty = target[1];
    if (sx < 0 || sx >= N || sy < 0 || sy >= N || tx < 0 || tx >= N || ty < 0 || ty >= N || blocked.count((ULL) sx * N + sy) || seen.count((ULL) sx * N + sy)) return 0;
    seen.insert((ULL) sx * N + sy);
    if (seen.size() > 20000 || (sx == target[0] && sy == target[1])) return 1;
    for (auto& dir : dirs) {
      vector<int> next = {sx + dir[0], sy + dir[1]};
      if (dfs(next, target, seen)) return 1;
    }
    return 0;
  }
};

func isEscapePossible(blocked [][]int, source []int, target []int) bool {
  const N = 1e6
  dirs := [4][2]int{{0, -1}, {0, 1}, {1, 0}, {-1, 0}}
  block := make(map[int]bool)
  for _, b := range blocked {
    block[b[0]*N+b[1]] = true
  }
  var dfs func(source, target []int, seen map[int]bool) bool
  dfs = func(source, target []int, seen map[int]bool) bool {
    sx, sy := source[0], source[1]
    tx, ty := target[0], target[1]
    if sx < 0 || sx >= N || sy < 0 || sy >= N || tx < 0 || tx >= N || ty < 0 || ty >= N || block[sx*N+sy] || seen[sx*N+sy] {
      return false
    }
    seen[sx*N+sy] = true
    if len(seen) > 20000 || (sx == target[0] && sy == target[1]) {
      return true
    }
    for _, dir := range dirs {
      next := []int{sx + dir[0], sy + dir[1]}
      if dfs(next, target, seen) {
        return true
      }
    }
    return false
  }
  s1, s2 := make(map[int]bool), make(map[int]bool)
  return dfs(source, target, s1) && dfs(target, source, s2)
}

use std::collections::{ HashSet, VecDeque };

const BOUNDARY: i32 = 1_000_000;
const MAX: usize = 20000;

impl Solution {
  pub fn is_escape_possible(blocked: Vec<Vec<i32>>, source: Vec<i32>, target: Vec<i32>) -> bool {
    let mut block = HashSet::with_capacity(blocked.len());
    for b in blocked.iter() {
      block.insert((b[0], b[1]));
    }
    bfs(&block, &source, &target) && bfs(&block, &target, &source)
  }
}

fn bfs(block: &HashSet<(i32, i32)>, source: &Vec<i32>, target: &Vec<i32>) -> bool {
  let dir = vec![(-1, 0), (1, 0), (0, -1), (0, 1)];

  let mut queue = VecDeque::new();
  let mut vis = HashSet::new();
  queue.push_back((source[0], source[1]));
  vis.insert((source[0], source[1]));

  while !queue.is_empty() && vis.len() < MAX {
    let (x, y) = queue.pop_front().unwrap();
    if x == target[0] && y == target[1] {
      return true;
    }
    for (dx, dy) in dir.iter() {
      let (nx, ny) = (x + dx, y + dy);
      if
        nx < 0 ||
        nx >= BOUNDARY ||
        ny < 0 ||
        ny >= BOUNDARY ||
        vis.contains(&(nx, ny)) ||
        block.contains(&(nx, ny))
      {
        continue;
      }
      queue.push_back((nx, ny));
      vis.insert((nx, ny));
    }
  }

  vis.len() >= MAX
}