这个原题是什么？是不是二维迷宫两点间的最短路？

" border="0" />

这个我没用广搜,广搜如果加上去重其实与我这个程序的时间差不多,但是我的这个算法空间要小许多,广搜如果不加去重,时间效率很低

怎么可能呢？105那题我就直接用的广搜，不过你是怎么写的广搜偶不太懂。。。
对了，原题样例有修改，你再看看

" border="0" />

原题是自娱自乐，写了个2D走迷宫的代码，用的是进站出站遍历整个迷宫的方法，但不是最短路径，孔明给了我一个最短路径的方法，我看了一段时间，觉得挺有意思，但是不知道这个算法是怎么来的。所以想问问。

综上，题目就是2d迷宫从指定起点到指定终点的最短路径。

另外，此帖好像和我没多大关系啊，难道是错觉？

[[it] 本帖最后由 SNAKEQX 于 2008-4-19 09:46 编辑 [/it]]

不知道...明天竞赛完了有时间去看看,不过我的广搜都是只要不加去重速度有时很慢,或者是队列暴了,循环队列也能暴了,我的广搜框架和思想都是从信息学竞赛教程上看的~

算法为
d[x][y]=min{ d[x+1][y] , d[x-1][y], d[x][y-1], d[x][y+1] };
且保证d[x][y]!=0
算法直接来自单向的路径数的DP，只不过加了一维
算法复杂度在O(N^2)与O(N^3)之间

[[it] 本帖最后由 卧龙孔明 于 2008-4-19 10:01 编辑 [/it]]

d[x][y]=max{ d[x+1][y] , d[x-1][y], d[x][y-1], d[x][y+1] };？？？
不是min????
d代表什么呢？

看了一下楼主注释的代码，楼主学习很用心啊！

这个程序的算法思想在１６＃帖的，是动态规划
至于注释中的一个问题：为什么不用９００而用１０００，其实，最大的肯定是比这两个数小，只要附一个比最大路径还大的就可以，例如是１２００，２０００等，都可以

笔误，不好意思，是min

为啥不是x*y？每个点最多被计算一次，转移代价还是O(1)

" border="0" />