📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3955| 回复: 12
跳转到指定楼层
上一主题 下一主题
收起左侧

[高频题] 无限大grid上找最短路径问题

全局:
高频题
公司名称: lyft

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
今天碰到了一道求最短路径的问题, 没有想通, 希望大家能给点思路在一个无限大的grid上,找出从origin到destination的最短路径,在grid里面,会有一些障碍点(block points) 和 lasers(block lines), 激光是以所在点的位置和发射方向表示的,问如何找到origin到dest的最短路径

感谢大家 会加米!

上一篇:LeetCode 宕机
下一篇:[用Java的SDE都需要读的] Java Essential Classes
推荐
mint0715 2019-11-22 07:06:45 | 只看该作者
全局:
Ericson1995 发表于 2019-11-22 04:53
请问怎么判断这个点被激光穿过呢?

一个激光,起点a, b,方向k, j。
那么这个激光的直线方程就是: (x-a)*j - (y-b)*k = 0

你需要检查:
1. 方格是否在直线上
对于一个格子的四个角,这四个角的坐标代进方程,全都大于0(或全都小于0),那么这个方格的四个顶点都在直线的某一侧,它一定不会被射到。如果既有大于0,又有小于0,那么:
2. 方格的四个顶点分布在直线的两侧->方格被直线穿过。(但未必被射线穿过,可能在射线反方向被穿过)
用方格的四条边方程代入方程,易得四个交点。如果任何一个交点满足1.他在方格上 2.他的x值满足x = a+kt且t>0,那么这个方块就被射线穿过。

评分

参与人数 1大米 +2 收起 理由
Ericson1995 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

推荐
0xff 2019-11-20 08:04:29 来自APP | 只看该作者
全局:
同时从起始点和终点做BFS?
回复

使用道具 举报

🔗
 楼主| Ericson1995 2019-11-20 08:06:10 | 只看该作者
全局:
0xff 发表于 2019-11-20 08:04
同时从起始点和终点做BFS?

laser的问题怎么解决呢?
回复

使用道具 举报

🔗
337845818 2019-11-20 23:53:13 | 只看该作者
全局:
题基本看不懂, 不明白激光是什么意思, 限制是什么

如果一定要给个答案就是a*
回复

使用道具 举报

🔗
 楼主| Ericson1995 2019-11-21 07:55:41 | 只看该作者
全局:
337845818 发表于 2019-11-20 23:53
题基本看不懂, 不明白激光是什么意思, 限制是什么

如果一定要给个答案就是a*

激光就是阻隔的线 相当于这条线上无法通行 给的激光是有发射点和发射方向
回复

使用道具 举报

🔗
593965536 2019-11-21 08:21:03 | 只看该作者
全局:
先处理一下图,把不能通行的点标记出来。
然后A*,dijstra,BFS/DFS 三种方法都可以,A*最佳
回复

使用道具 举报

全局:
激光可以穿透障碍点么
回复

使用道具 举报

🔗
 楼主| Ericson1995 2019-11-21 21:36:43 | 只看该作者
全局:
snail8844 发表于 2019-11-21 12:42
激光可以穿透障碍点么

可以穿过
回复

使用道具 举报

🔗
ljhgod 2019-11-21 23:40:58 | 只看该作者
全局:
593965536 发表于 2019-11-21 08:21
先处理一下图,把不能通行的点标记出来。
然后A*,dijstra,BFS/DFS 三种方法都可以,A*最佳

无限大的图怎么标激光
回复

使用道具 举报

🔗
ljhgod 2019-11-21 23:52:21 | 只看该作者
全局:
Ericson1995 发表于 2019-11-20 08:06
laser的问题怎么解决呢?

做两个dictionary,横的激光 竖的激光, key是激光x或有轴值,value 是激光坐标方向的list。
每bfs一点检查这一点横纵有没有激光,如果有会不会被射到

如果激光封锁掉,走不过去怎么判断呢?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表