1036.逃离大迷宫

链接：1036.逃离大迷宫
难度：Hard
标签：深度优先搜索、广度优先搜索、数组、哈希表
简介：只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。

题解 1 - typescript

• 编辑时间：2022-01-11
• 执行用时：1556ms
• 内存消耗：59.4MB
• 编程语言：typescript
• 解法介绍：bfs,判断是否被包围。

const format = (row: number, col: number) => `${row}:${col}`;
const dirs: number[][] = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
];
const MAX = 10 ** 6;
const MAX_CNT = 200 * 200;
function check(blocked: Set<string>, source: number[], target: number[]): boolean {
  const set = new Set<string>();
  const queue: number[][] = [[source[0], source[1]]];
  let cnt = MAX_CNT;
  while (queue.length) {
    const [row, col] = queue.shift()!;
    for (const [addrow, addcol] of dirs) {
      const nrow = row + addrow;
      const ncol = col + addcol;
      const str = format(nrow, ncol);
      if (nrow < 0 || nrow >= MAX || ncol < 0 || ncol >= MAX || blocked.has(str) || set.has(str))
        continue;
      if (--cnt == 0 || (nrow === target[0] && ncol === target[1])) return true;
      set.add(str);
      queue.push([nrow, ncol]);
    }
  }
  return false;
}
function isEscapePossible(blocked: number[][], source: number[], target: number[]): boolean {
  if (blocked.length <= 1) return true;
  const blocked_set = new Set(blocked.map(([row, col]) => format(row, col)));
  return check(blocked_set, source, target) && check(blocked_set, target, source);
}