当前在线人数16336
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
Re: 请教G家新题 continental divider
[版面:待字闺中][首篇作者:xykid1986] , 2015年02月05日21:12:56 ,次阅读,次回复
来APP回复,赚取更多伪币 关注本站公众号:
[首页] [上页][下页][末页] [分页:1 2 3 ]
xykid1986
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: xykid1986 (老苏), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Thu Feb  5 21:12:56 2015, 美东)

mark
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
ShaMiMa
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: ShaMiMa (啥密码?), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Thu Feb  5 21:35:19 2015, 美东)

对每个点,把比它小的改成零,比它大的当成山。如果能到每个零,这个点就是一个解。
行吗?

【 在 xm1223 (天天想上) 的大作中提到: 】
: continental divider
: 给一个矩阵,其中0代表海洋,其他数字代表高度,秉着水往低处流的原则,求出能够
: 流向任意海洋的点。 比如说
: 0 0 0 1 2 3 0
: 0 1 2 2 4 3 2
: 2 1 1 3 3 2 0
: 0 3 3 3 2 3 3
: 那么就要给出 第二行的4 (这有这点出发,能够找到连通道四个0的区域的一条非递增
: 路线),当然也有可能找不到这样的点,或者找到多个点。

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 167.]

 
yztree
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: yztree (云兆树), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Thu Feb  5 22:49:22 2015, 美东)

这个时间复杂度至少O(N^4)吧?

【 在 ShaMiMa (啥密码?) 的大作中提到: 】
: 对每个点,把比它小的改成零,比它大的当成山。如果能到每个零,这个点就是一个
解。
: 行吗?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
shuiya
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: shuiya (shuiya), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Thu Feb  5 23:11:11 2015, 美东)

首先想到的是从每一个海洋往外做BFS,找所有可能的来源留下记号。最后的结果应该
是找到一个留下了各个海洋的记号的那些点就是了。这样做的复杂度应该是O(kn^2),k
是海洋的个数。很显然这个不是最优解,因为有很多陆地的地方被做了几遍BFS,很浪
费。所以面试时候应该边写着这个算法边考虑能不能每个点只往外做一次BFS呢?
一种想法是第一次走的时候把以后BFS的结果都记录下来。但是好像没什么用。另一种
想法是这个点做BFS的时候已经知道了能往哪些个海洋里流。这个看起来靠谱。顺着想
也就是说当一个陆地上的点已经被标注的次数和他周围下坡的次数相等的时候才在这个
点做BFS。
流程大约是:
先扫一遍所有的海洋(0),把同一个海洋里的所有点标上同一个数。
建一个队列Q,队列里加上所有的海洋点。
LOOP:对队列里的第一个点做一层BFS,也就是找他的“上坡或平路”邻居,都标上和自
己相同的数(有可能自己已经被标了好几次,要都标上)。
对所有的邻居检查是否符合上文的展开BFS的条件(标注个数==周围下坡数)如果符合
就推到Q里面去。

一直做这个loop直到Q空了。扫一遍所有点看哪个点被标了所有的海洋标号。
如果平路能流 可能出现循环的依赖 可能需要再检查下平路。

这种做法的复杂度应该是O(n^2)吧。

上面是个初步的想法,欢迎讨论。

改正,加入q的条件是这个点已经被到达的次数等于了周围下坡的邻居数


--
※ 修改:·shuiya 於 Feb  5 23:53:41 2015 修改本文·[FROM: 209.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 73.]

 
pulpfree
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: pulpfree (pulpfree), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Thu Feb  5 23:12:43 2015, 美东)

O(N^4)不就是brute force吗?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 69.]

 
yztree
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: yztree (云兆树), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Thu Feb  5 23:37:06 2015, 美东)

海洋数最坏可能为O(N^2).
下坡数最多是四吧?

【 在 shuiya (shuiya) 的大作中提到: 】
: 首先想到的是从每一个海洋往外做BFS,找所有可能的来源留下记号。最后的结果应该
: 是找到一个留下了各个海洋的记号的那些点就是了。这样做的复杂度应该是O(kn^2),
k
: 是海洋的个数。很显然这个不是最优解,因为有很多陆地的地方被做了几遍BFS,很浪
: 费。所以面试时候应该边写着这个算法边考虑能不能每个点只往外做一次BFS呢?
: 一种想法是第一次走的时候把以后BFS的结果都记录下来。但是好像没什么用。另一种
: 想法是这个点做BFS的时候已经知道了能往哪些个海洋里流。这个看起来靠谱。顺着想
: 也就是说当一个陆地上的点已经被标注的次数和他周围下坡的次数相等的时候才在这个
: 点做BFS。
: 流程大约是:
: 先扫一遍所有的海洋(0),把同一个海洋里的所有点标上同一个数。
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
njusz
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: njusz (sz), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 11:31:27 2015, 美东)

不太懂,下坡数和标注个数或者海洋个数有什么关系?

我觉得每次每个海洋都bfs一层,然后可以用set/map合并下一步的点,
比如海洋1和海洋2这一层都bfs到一个点,可以标记为12,这样这个点以后bfs到的都标
记为12,表示可以到海洋1和2


【 在 shuiya (shuiya) 的大作中提到: 】
: 首先想到的是从每一个海洋往外做BFS,找所有可能的来源留下记号。最后的结果应该
: 是找到一个留下了各个海洋的记号的那些点就是了。这样做的复杂度应该是O(kn^2),
k
: 是海洋的个数。很显然这个不是最优解,因为有很多陆地的地方被做了几遍BFS,很浪
: 费。所以面试时候应该边写着这个算法边考虑能不能每个点只往外做一次BFS呢?
: 一种想法是第一次走的时候把以后BFS的结果都记录下来。但是好像没什么用。另一种
: 想法是这个点做BFS的时候已经知道了能往哪些个海洋里流。这个看起来靠谱。顺着想
: 也就是说当一个陆地上的点已经被标注的次数和他周围下坡的次数相等的时候才在这个
: 点做BFS。
: 流程大约是:
: 先扫一遍所有的海洋(0),把同一个海洋里的所有点标上同一个数。
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 130.]

 
Mephisto1527
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: Mephisto1527 (???), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 11:59:32 2015, 美东)

好想法, 感觉是正解。

【 在 shuiya (shuiya) 的大作中提到: 】
: 首先想到的是从每一个海洋往外做BFS,找所有可能的来源留下记号。最后的结果应该
: 是找到一个留下了各个海洋的记号的那些点就是了。这样做的复杂度应该是O(kn^2),
k
: 是海洋的个数。很显然这个不是最优解,因为有很多陆地的地方被做了几遍BFS,很浪
: 费。所以面试时候应该边写着这个算法边考虑能不能每个点只往外做一次BFS呢?
: 一种想法是第一次走的时候把以后BFS的结果都记录下来。但是好像没什么用。另一种
: 想法是这个点做BFS的时候已经知道了能往哪些个海洋里流。这个看起来靠谱。顺着想
: 也就是说当一个陆地上的点已经被标注的次数和他周围下坡的次数相等的时候才在这个
: 点做BFS。
: 流程大约是:
: 先扫一遍所有的海洋(0),把同一个海洋里的所有点标上同一个数。
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 199.]

 
heteroclinic
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: heteroclinic (asymptotically stable), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 12:04:56 2015, 美东)

Does it consider Caspian an ocean?

Or australian a continent?

In case of NPE
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 173.]

 
Mephisto1527
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: Mephisto1527 (???), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 12:08:10 2015, 美东)

可以把入Q的条件改成:所有的平或低邻居都已经处理过么?可以利用count来做这个。
然后Q实际上变成一个以未处理低平邻居为key, key = 0, 1, 2, 3, 4的buckets。这样
避免大排序,每次O(1)

【 在 shuiya (shuiya) 的大作中提到: 】
: 首先想到的是从每一个海洋往外做BFS,找所有可能的来源留下记号。最后的结果应该
: 是找到一个留下了各个海洋的记号的那些点就是了。这样做的复杂度应该是O(kn^2),
k
: 是海洋的个数。很显然这个不是最优解,因为有很多陆地的地方被做了几遍BFS,很浪
: 费。所以面试时候应该边写着这个算法边考虑能不能每个点只往外做一次BFS呢?
: 一种想法是第一次走的时候把以后BFS的结果都记录下来。但是好像没什么用。另一种
: 想法是这个点做BFS的时候已经知道了能往哪些个海洋里流。这个看起来靠谱。顺着想
: 也就是说当一个陆地上的点已经被标注的次数和他周围下坡的次数相等的时候才在这个
: 点做BFS。
: 流程大约是:
: 先扫一遍所有的海洋(0),把同一个海洋里的所有点标上同一个数。
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 199.]

 
Mephisto1527
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: Mephisto1527 (???), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 12:14:52 2015, 美东)

想法是一样的,只是这样的有个问题。

这个例子里面 最左边和最上的是位置标号。
假设1,2按照图示路径流,5次后,它们到[2,1]位置相遇,这时候因为2走快了,所以[3
,1] [3,2] [3,3]都需要更新。这样的情况极端的话会影响复杂度。


  0 1 2 3 4 5  
0 x x x x x x
1 x 1 1 1 1 1
2 2 2 x x x x
3 x 2 2 2 x x

下坡数和标注个数是为了让bfs按拓扑排序,让已经处理过的点已经包含所有能到达它
的海洋信息。


【 在 njusz (sz) 的大作中提到: 】
: 不太懂,下坡数和标注个数或者海洋个数有什么关系?
: 我觉得每次每个海洋都bfs一层,然后可以用set/map合并下一步的点,
: 比如海洋1和海洋2这一层都bfs到一个点,可以标记为12,这样这个点以后bfs到的都标
: 记为12,表示可以到海洋1和2
: k



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 199.]

 
njusz
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: njusz (sz), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 13:12:47 2015, 美东)

你的意思是等这个点所有可能的bfs都到齐了再继续bfs吧,比如你的例子里[2,1]开始
标2的时候先不bfs,等1到了再继续1的bfs。

但这样有可能碰到“死谷”吧,比如
3 3 3
3 1 3
0 2 4
这样2就一直再等1,不继续4吗?

【 在 Mephisto1527 (???) 的大作中提到: 】
: 想法是一样的,只是这样的有个问题。
: 这个例子里面 最左边和最上的是位置标号。
: 假设1,2按照图示路径流,5次后,它们到[2,1]位置相遇,这时候因为2走快了,所以
[3
: ,1] [3,2] [3,3]都需要更新。这样的情况极端的话会影响复杂度。
:   0 1 2 3 4 5  
: 0 x x x x x x
: 1 x 1 1 1 1 1
: 2 2 2 x x x x
: 3 x 2 2 2 x x
: 下坡数和标注个数是为了让bfs按拓扑排序,让已经处理过的点已经包含所有能到达它
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 130.]

 
Mephisto1527
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 13 ]

发信人: Mephisto1527 (???), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 13:36:18 2015, 美东)

漂亮的反例!:)
那看来第一轮除了海洋点之外,还要加入低(不能为平,否则还是死谷互锁)邻居数为
0的点,像死谷这种代表的是无海洋,当然也可以认为海洋点就是低邻居数为0的点。
处理平的情况还需要想想。

还有个想法,如果高度的数目有限,是不是可以按照高度入桶,从下向上淹,然后相当
于起点在不同海洋的小人(或无海洋)从不同路径向上躲,最后如果一个点把来自所有海洋
的小人凑齐了就算一个输出。

【 在 njusz (sz) 的大作中提到: 】
: 你的意思是等这个点所有可能的bfs都到齐了再继续bfs吧,比如你的例子里[2,1]开始
: 标2的时候先不bfs,等1到了再继续1的bfs。
: 但这样有可能碰到“死谷”吧,比如
: 3 3 3
: 3 1 3
: 0 2 4
: 这样2就一直再等1,不继续4吗?
: [3




--
※ 修改:·Mephisto1527 於 Feb  6 13:37:23 2015 修改本文·[FROM: 199.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 199.]

 
shuiya
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 14 ]

发信人: shuiya (shuiya), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 13:43:09 2015, 美东)

呃 我的回复点歪了。。。给你了短信。。。 麻烦你贴出来好么。。。

【 在 njusz (sz) 的大作中提到: 】
: 你的意思是等这个点所有可能的bfs都到齐了再继续bfs吧,比如你的例子里[2,1]开始
: 标2的时候先不bfs,等1到了再继续1的bfs。
: 但这样有可能碰到“死谷”吧,比如
: 3 3 3
: 3 1 3
: 0 2 4
: 这样2就一直再等1,不继续4吗?
: [3



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 131.]

 
hlight
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 15 ]

发信人: hlight (hlight), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 13:44:32 2015, 美东)

上面说从每一个海洋往外做BFS的我有点不太明白,象下面这种情况如何处理?

3 3 3 3 x 4
3 4 4 4 4 0
3 3 3 3 3 3

如 x=3 BFS如何断定x能够流到海洋?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
njusz
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 16 ]

发信人: njusz (sz), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 13:57:57 2015, 美东)

ok

寄信人: shuiya (shuiya)
标  题: Re: 请教G家新题  continental divider
发信站: 未名空间 (Fri Feb  6 13:40:33 2015)
来  源: 131.

不好意思一直忙别的事。是会出现这种情况但也比较容易fix,就是在能扩展的点都做
完了之后,再做所有没做过BFS的。然后还是遵循Q里面有就先做Q里的,没有就弄没做
BFS的。这个对复杂度没有影响。
还有就是这种情况平路的话能循环的依赖,也是要平路的BFS一下。
3 3 3 3 3 3
3 0 3 3 0 3
3 3 3 3 3 3
但是不管怎么说都是保证每个点BFS一次。关键是做BFS的顺序
就是说复杂度也就是O(n^2)的不变。

我是真的觉得这种题对于我来说真的很难的面试了。我只能写出我帖子里说的第一种做
法,写代码的时候应该能想出这种优化的。但一个小时肯定不够我再写这种的和处理些
特殊情况。

【 在 shuiya (shuiya) 的大作中提到: 】
: 呃 我的回复点歪了。。。给你了短信。。。 麻烦你贴出来好么。。。


--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 130.]

 
Mephisto1527
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 17 ]

发信人: Mephisto1527 (???), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 14:02:53 2015, 美东)

从大家发的面经来看,好像海洋的定义一般是四个边缘,或者两个边缘等。
看你这个例子,你可能认为0是海洋。
不过bfs方法一样的。

从0点开始,如果周围比自身高,就代表可以从那个地方流到自己,然后把这个集合bfs。
或者如果把高度理解成深度,可以变成从0点可以流到的任何地方。
你的例子中
第一次0 可以流到3 4 4,
第二次 上面的4不能扩展,因为没有比它不大的邻居;左边的4可以继续向左扩展;下
面的3可以向左扩展。
这样持续BFS,第二次中左边的4扩展到你图中最左边的4就截止了
而3则可以辗转扩展到x左边的3。
如果x=3,经由x左边的3就可以扩到x。
当然如果x>=4从4就bfs到x了。
x<=2则不可能到x。


【 在 hlight (hlight) 的大作中提到: 】
: 上面说从每一个海洋往外做BFS的我有点不太明白,象下面这种情况如何处理?
: 3 3 3 3 x 4
: 3 4 4 4 4 0
: 3 3 3 3 3 3
: 如 x=3 BFS如何断定x能够流到海洋?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 199.]

 
njusz
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 18 ]

发信人: njusz (sz), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 14:04:00 2015, 美东)

我觉得ls的方法可以解决死谷问题,就是按你说的比较访问次数和下坡次数,如果不同
,并不扔掉,只是放到queue后面去,这样等queue的size稳定的时候再忽略这个要求
pop出一个来,继续bfs,直到queue为空。

【 在 Mephisto1527 (???) 的大作中提到: 】
: 漂亮的反例!:)
: 那看来第一轮除了海洋点之外,还要加入低(不能为平,否则还是死谷互锁)邻居数为
: 0的点,像死谷这种代表的是无海洋,当然也可以认为海洋点就是低邻居数为0的点。
: 处理平的情况还需要想想。
: 还有个想法,如果高度的数目有限,是不是可以按照高度入桶,从下向上淹,然后相当
: 于起点在不同海洋的小人(或无海洋)从不同路径向上躲,最后如果一个点把来自所有
海洋
: 的小人凑齐了就算一个输出。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 130.]

 
Mephisto1527
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 19 ]

发信人: Mephisto1527 (???), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 14:08:35 2015, 美东)

想了一下, 好像平路的不能简单的BFS。

举个例子,这里数字代表海洋,左边是海洋1,右边海洋2,所有路平路
1 1 1 1 1 1 1 2 2 2 2 2 2
相遇的时候不能只update相遇点,而是所有平路点要全部变成所有相关海洋的全集,就
要求把所有连通平路放一起处理。

所以如果说保证没有平的就太好了,这个如果真面要问一下可不可以没有平路。


【 在 njusz (sz) 的大作中提到: 】
: ok
: 寄信人: shuiya (shuiya)
: 标  题: Re: 请教G家新题  continental divider
: 发信站: 未名空间 (Fri Feb  6 13:40:33 2015)
: 来  源: 131.
: 不好意思一直忙别的事。是会出现这种情况但也比较容易fix,就是在能扩展的点都做
: 完了之后,再做所有没做过BFS的。然后还是遵循Q里面有就先做Q里的,没有就弄没做
: BFS的。这个对复杂度没有影响。
: 还有就是这种情况平路的话能循环的依赖,也是要平路的BFS一下。
: 3 3 3 3 3 3
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 199.]

 
Mephisto1527
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 20 ]

发信人: Mephisto1527 (???), 信区: JobHunting
标  题: Re: 请教G家新题  continental divider
发信站: BBS 未名空间站 (Fri Feb  6 14:10:59 2015, 美东)

我总觉得放到Q后面重新排队会影响复杂度。
还是哪里没想到?

【 在 njusz (sz) 的大作中提到: 】
: 我觉得ls的方法可以解决死谷问题,就是按你说的比较访问次数和下坡次数,如果不同
: ,并不扔掉,只是放到queue后面去,这样等queue的size稳定的时候再忽略这个要求
: pop出一个来,继续bfs,直到queue为空。
: 海洋



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 199.]

[首页] [上页][下页][末页] [分页:1 2 3 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996