前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-04-16:在一个10^6 * 10^6的网格中,source = [sx, sy]是出发位置

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

作者头像
福大大架构师每日一题
发布2022-06-04 10:32:36
3390
发布2022-06-04 10:32:36
举报

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编写。代码如下:

代码语言:javascript
复制
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代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_01_3_week/Code02_EscapeALargeMaze.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-04-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档