作者EdisonX (闭上眼的鱼)
站内Prob_Solve
标题[问题] Turbo 版老鼠走迷宫..
时间Tue Nov 6 15:42:11 2012
老鼠走迷宫是老到不能再老的问题，
有几个题目是网路上看到的面试题目，
但小弟却没想到解法，上网找了些资料，
说明并不非常详尽，於此请教各位先进意见。
[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 ，小弟实作上若有问题再回来请教，
谢谢各位先进不吝赐教，感激不尽。
--
就算把新鲜的肝拿回去，还是一样写码到秃头，加班到天亮。
你是不是想这麽做？是的话你就拿回去~ 拿啊！！
九世宅男 : 下辈子不要再让我干工程师了 ~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 180.177.76.161
※ 编辑: EdisonX 来自: 180.177.76.161 (11/06 15:48)
1F：推 springman:最短路径应该是用 BFS、用 queue 不要用 stack。 11/06 16:08
2F：推 ledia:spanning tree + random weight ? 11/06 16:36
3F：→ EdisonX:先谢谢楼上两位给的 keyword, 我先 k 过相关资料, 感谢:) 11/06 17:09
4F：→ stimim:用 disjoint set 应该也可以？ 11/06 19:10
6F：→ firejox:我想会要求是奇数的话 就不会产生两倍宽的墙... 11/13 23:30
7F：→ firejox:有偶数就会有| ||的情形... 找最短路径应该可以用A*加速 11/13 23:31
8F：→ EdisonX:f 大给的版本和 bleed~ 大差蛮多的,谢谢您的回覆 :) 11/14 01:34