一个迷宫问题
迷宫问题：
一个n*n的迷宫：S’是起点，‘E’是终点，‘‘.’表示可以走，‘*’不能走，‘L’有钥匙才能走，‘k’代表钥匙，
（一个‘L’要消耗一个‘K’）：问你S能不能到E.......
如图实例：
n=5
E*LLK
L**LS
.LL.K
***.*
KK.L*

纠结了很久，DFS，BFS都试着做了、、、求具体算法思路！
题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=3582

[解决办法]
1) .和K的权为0，L的权为1。用Dijkstra算法,求出S起点到E和所有K的最短路径权
2) 设权为0的K节点有N(0)个，权为1的节点有N(1)个，..., E的权为P(E)
则当且仅当满足以下条件时S可以到E
对所有n=0,1,...,P(E)-1

C/C++ code

  n  ∑  N(i) >= (n+1) i=0
[解决办法]
回帖得10分。楼主再加点给我，好吗？
[解决办法]
好题目 日常回帖