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

请教 leetcode Unique Path II 变种,带障碍和jump point

全局:

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

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

x
题目可以参考 leetcode 62, 63 unique path I & II.

给一个n*m的 grid, 从0,0出发移动到n-1,m-1。
路上设有障碍点,不能走。
变种的地方就是
同时告诉你一些跳跃点, 比如((p1,p2),(p3,p4)),表示p1点可以跳到p2, p3点可以跳到p4。
问有多少总走法能走到终点。

大家能不能提供一些思路 谢谢了



上一篇:有近期准备脸家的面试的,组队刷题吗?
下一篇:求教一道题:c++一个2维平面上有一个点P0和其他一堆点(n个),找出距离P0最近的 ...
🔗
Onedayw 2017-2-13 04:46:45 | 只看该作者
全局:
原题方法是如果知道(x, y)的方法数是n,那就(x+1, y) += n; (x, y+1) += n;
变种就在这个基础上搜跳跃点有没有从(x, y)开始的,有的话比如说(x, y)调到(a, b),那就(a, b) += n;
不知道对不对
回复

使用道具 举报

🔗
jigsaw_Becky 2017-2-13 05:13:00 | 只看该作者
全局:
照样用DP,建立一个二维数组
如果在(x,y)处有障碍,dp[x][y] = 0
如果在 (x,y)处没有障碍, dp[x][y] = dp[x-1][y]+dp[x][y-1] + dp[i][j] .... 就是左边+上边+所有其他点可以跳到(x,y)处的点
回复

使用道具 举报

🔗
 楼主| l4zhou 2017-2-13 08:00:06 | 只看该作者
全局:
jigsaw_Becky 发表于 2017-2-13 05:13
照样用DP,建立一个二维数组
如果在(x,y)处有障碍,dp[x][y] = 0
如果在 (x,y)处没有障碍, dp[x][y] =  ...

假如从 3,3 跳到1,1。
dp[1][1] = dp[0][1]+dp[1][0] + dp[3][3]
bottom up来算DP的话,算dp[1][1]的时候 dp[3][3]还没算呢?
回复

使用道具 举报

🔗
jigsaw_Becky 2017-2-13 08:24:54 | 只看该作者
全局:
l4zhou 发表于 2017-2-13 08:00
假如从 3,3 跳到1,1。
dp[1][1] = dp[0][1]+dp[1][0] + dp[3][3]
bottom up来算DP的话,算dp[1][1] ...

那这样呢:
先按照unique path II来做,不考虑可以跳的情况。
然后比如说A可以跳到C, B可以跳到C,C可以跳到D。算这些点的indegree和outdegree。这里A和B的indegree是0,outdegree是1. C的indegree是2,outdegree是1。。。。把indegree==0, outdegree>0的点放到一个queue里面,这里就是A, B。每次poll()一个点出来,比如A,那么C的步数就是原来的步数加A的步数,C的indegree -= 1,如果indegree==0又可以放到queue里面。。。。
这样感觉可以做出来吧?就是不知道有没有更简洁的方法。这些可以互相跳来跳去的点应该是不会形成环的吧,比如说A可以跳到B,B又可以跳到A,那就可以一直跳来跳去了。。。。这个方法也就不对了。。。
回复

使用道具 举报

🔗
stellari 2017-2-14 07:04:50 | 只看该作者
全局:
这题得先恐怕还是需要一些额外的限制条件,因为只要(p1, p2)中的p2在p1之前的话,那就可以在p1->p2之间来回兜任意多次圈子。如果每多兜一圈都算一个新的unique path,那么出现这种情况时基本上答案都是无穷大(除非某些情况下,从p2出发因为障碍物原因无法走到p1)。所以要让这题自洽,必须进一步加上某些限制,比如:

1. p2只能出现在p1之后
2. 已经使用过的跳跃点不能再使用第二次
3. 重新定义unique path的概念
……







回复

使用道具 举报

🔗
 楼主| l4zhou 2017-2-14 07:19:51 | 只看该作者
全局:
stellari 发表于 2017-2-14 07:04
这题得先恐怕还是需要一些额外的限制条件,因为只要(p1, p2)中的p2在p1之前的话,那就可以在p1->p2之间来回 ...

往回跳答案就是无穷大,
只要不往回跳就没问题。
回复

使用道具 举报

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

本版积分规则

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