一个20*20迷宫搜索问题

zhuceyongde 发表于 2009-4-5 09:08:44

地图（MAP），
地图是用一个二维数组表示的。数组里的值代表地图上对应的道路、墙壁、或者宝物。

大门位于地图的 (0,0) 点（左上角）。开始的时候位于这个点，结束的时候也必须回到这个点。

可以向上下左右四个方向移动。如果移动的目标是墙壁或者宝库的边界，那么移动不会成功。如果移动的目标点上有宝物，那么宝物会自动被拣起。每移动一次就算是走了1步。

有步数限制，只能走N步，因此劳必须在N步之内（包括N步）回到大门处（坐标0,0点）。如果没能回来，就算任务失败。
要求在10秒内返回，并尽可能捡到多的宝物。

gxqcn 发表于 2009-4-5 09:16:36

这是图的搜索吧？
有DFS和BFS算法。

zhuceyongde 发表于 2009-4-5 11:56:46

有没有别的算法，DFS或BFS会超时，我想。

没——问题 发表于 2009-4-5 13:32:51

题目没说清楚阿
in和 out都是什么？
假设输入地图，N
输出走法
我会bfs出一张以宝物为节点的图，并以步数为权值

zhuceyongde 发表于 2009-4-6 00:16:26

回复 4# 没——问题的帖子

输入是一张20*20的地图，用数字表示的，输出为由UP,DOWN,LEFT.RIGHT表示的从（0，0）出发并最终回到（0，0）的路径，尽可能的拾到更多的宝物。
能具体说说怎样以宝物为节点的图，并以步数为权值的吗？？

无心人 发表于 2009-4-6 08:18:43

宝物是隐藏的么？

zhuceyongde 发表于 2009-4-6 16:54:04

回复 6# 无心人的帖子

不是，若所走的方格内有宝物，则自动拾起。

无心人 发表于 2009-4-7 07:41:08

那好像是有最大长度限制的最短路径吧？？

zhuceyongde 发表于 2009-4-7 22:23:32

对，有最大步数限制，有什么好一点的想法吗。

northwolves 发表于 2009-5-31 22:04:49

要求在10秒内返回
-------------------------
这个什么意思？是不是还有速度限制？

页: [1] 2

数学研发论坛's Archiver