大家帮忙想个算法吧!

软件和网站开发以及相关技术探讨
头像
yy890521
帖子: 580
注册时间: 2008-11-09 18:07
来自: SCU

大家帮忙想个算法吧!

#1

帖子 yy890521 » 2009-09-23 13:20

有如下二维数组:

代码: 全选

      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这样连续递减的值的格子。
比如有“*”标记的路
这样的路径有几条找几条
要求,时间复杂度和空间复杂度越小越好。因为是在单片机上运行的,所以越精简越好
。。。。。。。。感觉好山寨。。。。。。。。。
头像
yy890521
帖子: 580
注册时间: 2008-11-09 18:07
来自: SCU

Re: 大家帮忙想个算法吧!

#2

帖子 yy890521 » 2009-09-23 13:32

顶上去
。。。。。。。。感觉好山寨。。。。。。。。。
Jayi
帖子: 9
注册时间: 2009-09-23 20:17

Re: 大家帮忙想个算法吧!

#3

帖子 Jayi » 2009-09-23 20:21

顶,
我只会最暴力的算法。。。
头像
wenstream
帖子: 186
注册时间: 2008-06-18 22:02

Re: 大家帮忙想个算法吧!

#4

帖子 wenstream » 2009-09-23 20:23

想当年面网易的时候有这条题目。。。。。。
友情顶一下
delectate
帖子: 18311
注册时间: 2008-01-09 22:41

Re: 大家帮忙想个算法吧!

#5

帖子 delectate » 2009-09-23 20:42

Jayi 写了:顶,
我只会最暴力的算法。。。
循环套循环吧……

我不会这个东西了……

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

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

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

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

条条大陆通罗马…… :em09
delectate
帖子: 18311
注册时间: 2008-01-09 22:41

Re: 大家帮忙想个算法吧!

#6

帖子 delectate » 2009-09-24 9:17

昨天睡不着觉,又想了想

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

如果有多个是-1的数,那么都遍历一次
头像
yy890521
帖子: 580
注册时间: 2008-11-09 18:07
来自: SCU

Re: 大家帮忙想个算法吧!

#7

帖子 yy890521 » 2009-09-24 11:19

delectate 写了:昨天睡不着觉,又想了想

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

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

PS:那个255就是死区,不用管它。
。。。。。。。。感觉好山寨。。。。。。。。。
头像
yy890521
帖子: 580
注册时间: 2008-11-09 18:07
来自: SCU

Re: 大家帮忙想个算法吧!

#8

帖子 yy890521 » 2009-09-24 19:04

在手动顶一下,还是没有找到合适的算法 :em20
。。。。。。。。感觉好山寨。。。。。。。。。
delectate
帖子: 18311
注册时间: 2008-01-09 22:41

Re: 大家帮忙想个算法吧!

#9

帖子 delectate » 2009-09-24 22:20

要不先生成所有路径,然后一次判断路径可行性?

继续关注!
头像
BigSnake.NET
帖子: 12522
注册时间: 2006-07-02 11:16
来自: 廣州
联系:

Re: 大家帮忙想个算法吧!

#10

帖子 BigSnake.NET » 2009-09-24 22:28

dp ..... 时间n^2, 空间 n
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。
头像
yy890521
帖子: 580
注册时间: 2008-11-09 18:07
来自: SCU

Re: 大家帮忙想个算法吧!

#11

帖子 yy890521 » 2009-09-25 12:56

BigSnake.NET 写了:dp ..... 时间n^2, 空间 n
dp算法?google一下
。。。。。。。。感觉好山寨。。。。。。。。。
头像
yy890521
帖子: 580
注册时间: 2008-11-09 18:07
来自: SCU

Re: 大家帮忙想个算法吧!

#12

帖子 yy890521 » 2009-09-25 13:26

BigSnake.NET 写了:dp ..... 时间n^2, 空间 n
不对哦,我的这个规则得出来的就是最短路径了,这里只是要找实现这个规则的方法。
。。。。。。。。感觉好山寨。。。。。。。。。
dshbusiness
帖子: 1831
注册时间: 2009-04-03 15:10

Re: 大家帮忙想个算法吧!

#13

帖子 dshbusiness » 2009-09-25 20:12

我觉得深搜和动态规划都可以解……
头像
BigSnake.NET
帖子: 12522
注册时间: 2006-07-02 11:16
来自: 廣州
联系:

Re: 大家帮忙想个算法吧!

#14

帖子 BigSnake.NET » 2009-09-25 20:18

yy890521 写了:
BigSnake.NET 写了:dp ..... 时间n^2, 空间 n
不对哦,我的这个规则得出来的就是最短路径了,这里只是要找实现这个规则的方法。
你是找路径总数还是所有路径
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。
Jayi
帖子: 9
注册时间: 2009-09-23 20:17

Re: 大家帮忙想个算法吧!

#15

帖子 Jayi » 2009-09-26 11:23

dshbusiness 写了:我觉得深搜和动态规划都可以解……
动态规划怎么解呢?
回复