> 我现在的思路是用dfs寻路,并尽量不走原路,<得出是否为唯一最短路径>
> 但是如何确定那些墙多余没有更好的办法,请哪位指点一二.
用BFS,首先设墙和题目已给的路径上的所有点为used，剩余点为unused，然后利用BFS算出从起点到除墙以外的那些点的最短距离，然后利用BFS算出从终点到除墙以外的那些点的最短距离。
（1）判断最短路径是否唯一
如果不唯一，对于那些unused的点，必存在一个点，从起点到这点的最短距离加上从终点到这点的最短距离等于题目给出的最短距离长度
（2）判断墙是否多余
检查题目给出的墙分隔的那些点对，对一个一个被墙分隔的点对(a1,b1),(a2,b2),如果分隔它们的墙是多余的，那么从起点到(a1,b1)的最短距离加上从终点到(a2,b2)的最短距离必大于题目给出的最短距离长度pathlen，且从起点到(a2,b2)的最短距离加上从终点到(a1,b1)的最短距离也必大于pathlen，也就是起点，(a1,b1),(a2,b2),终点不可能在一个最短路径上，也就没必要用墙分隔了

• 赞 很巧妙啊 (0) Isun 2008-10-16 22:59:20
• 绝对同意这个算法,很不错 (0) tzkq 2008-11-14 12:59:47
• Re:给个思路,如何判断那些墙多余?高人现身! (42) yzthz 2009-12-21 17:33:54
• Re:给个思路,如何判断那些墙多余?高人现身! (422) gtzygtzy 2010-01-20 23:48:54
• Re:给个思路,如何判断那些墙多余?高人现身! (8) walker01 2010-03-06 11:02:48
• 这个算法 妙不可言 (0) wujunfeng 2012-02-11 15:20:49
• Re:给个思路,如何判断那些墙多余?高人现身! (407) ringwan 2013-10-23 15:30:15
• 赞。就是这个思路。过了 (0) Liuzhaoliang 2014-10-20 04:43:55