2022-04-16：在一个10^6 * 10^6的网格中， source = [sx, sy]是出发位置，target

2022-04-16：在一个10^6 * 10^6的网格中， source = [sx, sy]是出发位置，target = [tx, ty]是目标位置， 数组blocked是封锁的方格列表，被禁止的方格数量不超过200， blocked[i] = [xi, yi] 表示(xi, yi)的方格是禁止通行的， 每次移动都可以走上、下、左、右四个方向， 但是来到的位置不能在封锁列表blocked上， 同时不允许走出网格。 如果从source能到达target返回 true。否则返回false。

答案2022-04-16：

宽度优先遍历。 n个×，围住n*(n-1)/2个格子。

代码用rust编写。代码如下：

use std::collections::HashSet;

fn main() {
    let blocked: Vec<Vec<isize>> = vec![vec![0, 1], vec![1, 0]];
    let source: Vec<isize> = vec![0, 0];
    let target: Vec<isize> = vec![0, 2];
    let ret: bool = isEscapePossible(blocked, source, target);
    println!("{}", ret);
}

const offset: isize = 1000000;

fn isEscapePossible(blocked: Vec<Vec<isize>>, source: Vec<isize>, target: Vec<isize>) -> bool {
    let n = blocked.len();
    let maxPoints: isize = (n * (n - 1) / 2) as isize;
    let mut blockSet: HashSet<isize> = vec![].into_iter().collect();
    for i in 0..n {
        blockSet.insert(blocked[i][0] * offset + blocked[i][1]);
    }
    return bfs(
        source[0], source[1], target[0], target[1], maxPoints, &blockSet,
    ) && bfs(
        target[0], target[1], source[0], source[1], maxPoints, &blockSet,
    );
}

fn bfs(
    fromX: isize,
    fromY: isize,
    toX: isize,
    toY: isize,
    maxPoints: isize,
    blockSet: &HashSet<isize>,
) -> bool {
    let mut visited: HashSet<isize> = vec![].into_iter().collect();
    let mut queue: Vec<isize> = Vec::new();
    visited.insert(fromX * offset + fromY);
    queue.push(fromX * offset + fromY);
    while queue.len() > 0 && (visited.len() as isize <= maxPoints) {
        let cur = queue[0];
        queue.remove(0);
        let curX = cur / offset;
        let curY = cur - curX * offset;
        if (findAndAdd(curX - 1, curY, toX, toY, blockSet, &mut visited, &mut queue)
            || findAndAdd(curX + 1, curY, toX, toY, blockSet, &mut visited, &mut queue)
            || findAndAdd(curX, curY - 1, toX, toY, blockSet, &mut visited, &mut queue)
            || findAndAdd(curX, curY + 1, toX, toY, blockSet, &mut visited, &mut queue))
        {
            return true;
        }
    }
    return visited.len() as isize > maxPoints;
}

// 来到的点，(row, col)
// 要寻找的目标点，toX， toY
// HashSet<Long> blockSet存着不能走的格子！障碍点！
// HashSet<Long> visited, Queue<Long> queue 为了宽度优先遍历服务的！
// visited，已经处理过的点，请不要重复的放入queue
// 如果已经到达了(toX， toY)
fn findAndAdd(
    row: isize,
    col: isize,
    toX: isize,
    toY: isize,
    blockSet: &HashSet<isize>,
    visited: &mut HashSet<isize>,
    queue: &mut Vec<isize>,
) -> bool {
    if (row < 0 || row == offset || col < 0 || col == offset) {
        return false;
    }
    if (row == toX && col == toY) {
        return true;
    }
    let value = row * offset + col;
    if !blockSet.contains(&value) && !visited.contains(&value) {
        visited.insert(value);
        queue.push(value);
    }
    return false;
}

执行结果如下：

左神java代码