在之前的一篇文章（迷宫营救公主算法）中提供了一个半成品的解决方案，之所以说他是半成品，是因为首先选择的算法就不对，采用的是深度优先搜索，其次也没有真正的用对深度优先算法，走过的点应该标记为已经走过，而不应该重复遍历该节点。下面的文章对于广度优先和深度优先两种算法的解释非常到位。今天准备把这个问题再完整的用正确的算法解答一遍。
文章链接：【图论】广度优先搜索和深度优先搜索。
就营救公主的问题而言，这里不再重复描述问题了，请点击这里查看题目分析：链接。这次选用广度优先算法来解决该问题。上面的算法介绍文章中对该算法已经分析得非常清晰了。先给解决本问题的算法伪代码：
这里每个节点有三种状态：
今天下班前在公司的技术题库中看到这道题目，思路很快就有了，递归遍历每一条可能的路径，然后找出最短的路径。回家把代码写出来了。发现算法效率实在是太低了，在矩阵较小的时候还好，当矩阵稍微大一点时根本算不过来，感觉复杂度像是O((N*M)^(N*M))这个数值太庞大了，也完全没有意义。公主等到花儿都谢啦。。
貌似这位同学的算法还不错，还没来得及研究，先做个链接：http://blog.csdn.net/joseph_1118/article/details/9390301
应付较小的矩阵下面的方法还是能蒙混过关的。先发到这里，后面再继续研究优化。题目和代码都在一起：
/**
* 公主被魔王抓走了，王子需要拯救出美丽的公主。他进入了魔王的城堡，魔王的城堡是一座很大的迷宫。
* 为了使问题简单化，我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙，王子不能通过。王子只
* 能移动到相邻（上下左右四个方向)的方格内，并且一秒只能移动一步。地图由’S’，’P’，’.’，’*’
* 四种符号构成，’.’表示王子可以通过，’*’表示墙，王子不能通过；’S’表示王子的位置；’P’表示公主
* 的位置；T表示公主存活的剩余时间，王子必须在T秒内到达公主的位置，才能救活公主。如下图所示：
*/
Loading ...
