PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Prob_Solve
[问题] Turbo 版老鼠走迷宫..
楼主:
EdisonX
(卡卡兽)
2012-11-06 15:42:11
老鼠走迷宫是老到不能再老的问题,
有几个题目是网络上看到的面试题目,
但小弟却没想到解法,上网找了些资料,
说明并不非常详尽,于此请教各位先进意见。
[0] 探讨的迷宫
迷宫种类很多,这个不赘述,我想探讨的主要只有一个特性,
迷宫内的任意两点一定可以相通。
[1] 寻找最短路径
假设一条迷宫不只一条唯一路径,也有可能造成回路,
给定入口与出口,请问怎么找出最短路径?
[2] 如何产生出一条迷宫
如何产生一条,具有唯一解,且任两点必相通的迷宫?
假设是 M x N,网络上是有种方法可以产生,但前提限制是,
M, N 必须为奇数 ( 为什么一定要奇数我也想不透,但实际跑偶数真的有问题),
请问是否有产生符合以下条件迷宫的方法?
(a) 出口 / 入口不用限制在边界上,可以设在迷宫内部
(b) 任两点必定相通
(c) M x N,M, N >2,For All M, N
(d) 不会造成回路,且只有唯一一条路径。
这种问法让我感到很不好意思,但想了半天真的是没什么想法 = =
唯一有“一点点”想法的是寻最短路径,“似乎”可以用 DP 解?
效率分析和实作就一直卡死。
小弟承认算法 / 资料结构没 k 完,请问要解上面两个问题,
是否该再补足哪些部份?
可指点个概念,或给些 keyword ,小弟实作上若有问题再回来请教,
谢谢各位先进不吝赐教,感激不尽。
作者:
springman
(司布林)
2011-01-06 16:08:00
最短路径应该是用 BFS、用 queue 不要用 stack。
作者:
ledia
(付出不需要理由)
2011-01-06 16:36:00
spanning tree + random weight ?
楼主:
EdisonX
(卡卡兽)
2011-01-06 17:09:00
先谢谢楼上两位给的 keyword, 我先 k 过相关资料, 感谢:)
作者:
stimim
(qqaa)
2011-01-06 19:10:00
用 disjoint set 应该也可以?
作者:
firejox
(Tangent)
2011-01-13 23:27:00
http://en.wikipedia.org/wiki/Maze_generation_algorithm
我想会要求是奇数的话 就不会产生两倍宽的墙...有偶数就会有| ||的情形... 找最短路径应该可以用A*加速
楼主:
EdisonX
(卡卡兽)
2011-01-14 01:34:00
f 大给的版本和 bleed~ 大差蛮多的,谢谢您的回复 :)
继续阅读
Re: [问题] Interview street: zombie march
neutrino
Re: [问题] Interview street: zombie march
Leon
Re: [问题] Interview street: zombie march
DJWS
Re: [问题] Interview street: zombie march
neutrino
[问题] 最短路径花O(E)
wsx02
Re: [问题] 中序语法如何转后序语法 ?
aioio1
Re: [问题] 中序语法如何转后序语法 ?
space5
[问题] 中序语法如何转后序语法 ?
aioio1
Re: [问题] Interview street: zombie march
neutrino
[问题] 时间复杂度
keke0421
Links
booklink
Contact Us: admin [ a t ] ucptt.com