作者bleed1979 (十三)
站内Prob_Solve
标题Re: [问题] Turbo 版老鼠走迷宫..
时间Wed Nov 7 07:30:22 2012
https://gist.github.com/4028447
http://codepad.org/lNFPCSe6
输入：
w 宽
h 高
r 一开始几个生长点
赶着上班回头在补内文。
Bleed
※ 引述《EdisonX (闭上眼的鱼)》之铭言：
: 老鼠走迷宫是老到不能再老的问题，
: 有几个题目是网路上看到的面试题目，
: 但小弟却没想到解法，上网找了些资料，
: 说明并不非常详尽，於此请教各位先进意见。
: [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: 114.25.242.134
1F：推 EdisonX:感谢 bleed1979 , 先研究看看, 谢谢 :) 11/07 22:41