＋设为首页 ＋添加到收藏夹
不知道数据结构上叫什么,自已想的,写了一个测试程序,似乎结果是正确的.哪位兄台指正一下.
新的算法是这样的:
1.随机产生由0x00和0xff结成的地图
2.建立一个空的"连通地图方格列表",然后用递归方法去搜索所有与(0,0)相同值且连通的方格,然后把坐格存入"连通地图方格列表"中,在递归时,如果碰到"连通地图方格列表"中已经存在的方格则跳出.这样,就产生了一个"连通地图方格列表",然后只要判断迷宫入口坐标(0,0)和出口坐标(MAXX,MAXY)是否都
在列表时就可以知道是否迷宫能走通了
3.把迷宫入口坐标(0,0)的赋值为1,然后用循环判断迷宫中每一方格,如果一个方格的值>1且小于255的话,则把相邻的方格值全部加1,如果某一个相邻方格的值比所在方格值+1还要大的话(因为连通
的原因),则把相邻方格设成方格值+1,重复这样做,直到 出口坐标(MAXX,MAXY) 也被赋值为止.
4.现在工作就很简单了,从出口坐标(MAXX,MAXY)开始向上推,逐次递减直到入口坐标(0,0),这样就得到了一个由多个坐标组成的路线表,也就是最短路径了(看起来是的)
这样有问题吗?
楼主的好象就是Dijstra算法，你去看看那个算法吧，用贪心可以证明的．不过楼主能自己想出来，厉害！厉害！
方法是对的。
先用深度优先遍历判断连通性，然后用类似广度优先遍历的方法找最短路。
只是“循环判断迷宫中每一方格”并“重复这样做”比直接广度优先遍历要多花些时间。
这个题目好像USACO上面做过的一道……救公主的题目？
