当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 18 篇帖子 ]  前往页数 1, 2  下一页
作者 内容
1 楼 
 文章标题 : 大家帮忙想个算法吧!
帖子发表于 : 2009-09-23 13:20 
头像

注册: 2008-11-09 18:07
帖子: 580
地址: SCU
送出感谢: 0 次
接收感谢: 0 次
有如下二维数组:
代码:
      y
7  |255    14   15   16     15     12     13    14 *
6  |255    13   12   13     14     11*    12*   13*
5  |255    12   11   10     9     10*     255   255
4  |255    5    6     7     8      9*     255   255
3  |3*     4*   5*    6*    7*     8*     255   255
2  |2*     3    4     5     255    9      255   255
1  |1*     255  5     6     7      8      255   255
0  |0*     255  255   255   255    255    255   255
      ------------------------------------------------>x
    0       1    2     3     4      5      6     7


找出(7,7)到(0,0)的路径,路径必须是14-13-12-……-3-2-1-0这样连续递减的值的格子。
比如有“*”标记的路
这样的路径有几条找几条
要求,时间复杂度和空间复杂度越小越好。因为是在单片机上运行的,所以越精简越好


_________________
。。。。。。。。感觉好山寨。。。。。。。。。


页首
 用户资料  
 
2 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-23 13:32 
头像

注册: 2008-11-09 18:07
帖子: 580
地址: SCU
送出感谢: 0 次
接收感谢: 0 次
顶上去


_________________
。。。。。。。。感觉好山寨。。。。。。。。。


页首
 用户资料  
 
3 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-23 20:21 

注册: 2009-09-23 20:17
帖子: 9
送出感谢: 0 次
接收感谢: 0 次
顶,
我只会最暴力的算法。。。


页首
 用户资料  
 
4 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-23 20:23 
头像

注册: 2008-06-18 22:02
帖子: 186
送出感谢: 0 次
接收感谢: 1
想当年面网易的时候有这条题目。。。。。。
友情顶一下


页首
 用户资料  
 
5 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-23 20:42 

注册: 2008-01-09 22:41
帖子: 18311
送出感谢: 0 次
接收感谢: 6
Jayi 写道:
顶,
我只会最暴力的算法。。。

循环套循环吧……

我不会这个东西了……

貌似研究gps地图的,都接触过这个东西。

首先在x,y中判断死路(个人定义的名称,瞎起的……),到那里无路可走的。

然后划分出来死区(无可能的地方,大片的255什么的)

最后可选择的路,也就没多少了,每条都可以

条条大陆通罗马…… :em09


页首
 用户资料  
 
6 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-24 9:17 

注册: 2008-01-09 22:41
帖子: 18311
送出感谢: 0 次
接收感谢: 6
昨天睡不着觉,又想了想

只要判断起始数字周边8个数是起始数字-1的就可以顺着走下去。

如果有多个是-1的数,那么都遍历一次


页首
 用户资料  
 
7 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-24 11:19 
头像

注册: 2008-11-09 18:07
帖子: 580
地址: SCU
送出感谢: 0 次
接收感谢: 0 次
delectate 写道:
昨天睡不着觉,又想了想

只要判断起始数字周边8个数是起始数字-1的就可以顺着走下去。

如果有多个是-1的数,那么都遍历一次

这种方法想着很简单,但是计算机执行起来的效率貌似不高,又要建立一个堆栈,这是没有办法的办法咯
其实这还是一个简化了的模型,有些看似是能走通的路其实有墙壁相隔的,还要和数组的墙壁信息相结合才能判断出路径;所以如果这个简化了的模型找路都这么费劲的话,那单片机跑起来就痛苦了

PS:那个255就是死区,不用管它。


_________________
。。。。。。。。感觉好山寨。。。。。。。。。


页首
 用户资料  
 
8 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-24 19:04 
头像

注册: 2008-11-09 18:07
帖子: 580
地址: SCU
送出感谢: 0 次
接收感谢: 0 次
在手动顶一下,还是没有找到合适的算法 :em20


_________________
。。。。。。。。感觉好山寨。。。。。。。。。


页首
 用户资料  
 
9 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-24 22:20 

注册: 2008-01-09 22:41
帖子: 18311
送出感谢: 0 次
接收感谢: 6
要不先生成所有路径,然后一次判断路径可行性?

继续关注!


页首
 用户资料  
 
10 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-24 22:28 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
dp ..... 时间n^2, 空间 n


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
11 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-25 12:56 
头像

注册: 2008-11-09 18:07
帖子: 580
地址: SCU
送出感谢: 0 次
接收感谢: 0 次
BigSnake.NET 写道:
dp ..... 时间n^2, 空间 n

dp算法?google一下


_________________
。。。。。。。。感觉好山寨。。。。。。。。。


页首
 用户资料  
 
12 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-25 13:26 
头像

注册: 2008-11-09 18:07
帖子: 580
地址: SCU
送出感谢: 0 次
接收感谢: 0 次
BigSnake.NET 写道:
dp ..... 时间n^2, 空间 n

不对哦,我的这个规则得出来的就是最短路径了,这里只是要找实现这个规则的方法。


_________________
。。。。。。。。感觉好山寨。。。。。。。。。


页首
 用户资料  
 
13 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-25 14:16 
头像

注册: 2008-03-25 15:49
帖子: 25876
地址: 谁知道?
送出感谢: 8
接收感谢: 10
继续关注~~


页首
 用户资料  
 
14 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-25 20:12 

注册: 2009-04-03 15:10
帖子: 1831
送出感谢: 0 次
接收感谢: 0 次
我觉得深搜和动态规划都可以解……


页首
 用户资料  
 
15 楼 
 文章标题 : Re: 大家帮忙想个算法吧!
帖子发表于 : 2009-09-25 20:18 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
yy890521 写道:
BigSnake.NET 写道:
dp ..... 时间n^2, 空间 n

不对哦,我的这个规则得出来的就是最短路径了,这里只是要找实现这个规则的方法。


你是找路径总数还是所有路径


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 18 篇帖子 ]  前往页数 1, 2  下一页

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 3 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译