求A点到B点之间最短的一条路线(看谁速度最快)

apolloh · 发表于 2008-11-7 11:26

应该存在2条以上最短路程的可能。

yuanhongly · 发表于 2008-11-7 11:55

先占个楼来备用放我的答案思考中....哈哈

apolloh · 发表于 2008-11-7 12:09

原帖由 彭希仁 于 2008-11-6 16:26 发表

可以走,这样对题的难度不会增加,只要不是1直接到6就可以.

如果这样可以2-〉6为什么就不行呢？都是对角线，如果2-〉6可以那么1-〉6又怎么不行能？

是不是这个对角线还是不能算？

Tq-laoyu · 发表于 2008-11-7 12:36

功力不足，等答案！

joforn · 发表于 2008-11-7 12:43

如果1->5->9可以走，那么到底是空白单元表示路径还是-1表示路径？

HHAAMM · 发表于 2008-11-7 12:56

先看下27楼的内容
先大概来个思路（有些情况下会出错，怎么处理还没想好）
不知对不，但感觉就该这么解决这种问题
Sub abc()
Dim x%, y%
ar1 = Range("a2:ae32")
For x = 29 To 2 Step -1
For y = 30 To 2 Step -1
      If ar1(x, y) <> "" Then
         ar1(x, y) = ar1(x + 1, y) + ar1(x, y + 1)
         If ar1(x + 1, y) <> "" And ar1(x, y - 1) <> "" And ar1(x, y + 1) <> "" Then ar1(x, y) = 0
      End If
Next y
Next x
Range("a2:ae32") = ar1
[b2].Select
Selection.Interior.ColorIndex = 33
Do While Selection.Offset(0, 1) = "" Or Selection.Offset(0, 1) = Selection.Offset(1, 0) And Selection.Offset(1, 0) <> ""
Selection.Offset(1, 0).Select
Selection.Interior.ColorIndex = 33
Loop
If Selection.Offset(1, 0) <> "" And Selection.Offset(0, 1) <> "" Then
      If Selection.Offset(1, 0) < Selection.Offset(0, 1) Then
         Selection.Offset(1, 0).Select
      Else
         Selection.Offset(1, 0).Select
      End If
ElseIf Selection.Offset(1, 0) <> "" Then
      Selection.Offset(1, 0).Select
ElseIf Selection.Offset(0, 1) <> "" Then
      Selection.Offset(0, 1).Select
End If
Selection.Interior.ColorIndex = 33
Do While Selection.Row < 31
If Selection.Offset(1, 0) <> "" And Selection.Offset(0, 1) <> "" Then
      If Selection.Offset(1, 0) > Selection.Offset(0, 1) Then
         Selection.Offset(1, 0).Select
      Else
         Selection.Offset(0, 1).Select
      End If
ElseIf Selection.Offset(1, 0) <> "" Then
         Selection.Offset(1, 0).Select
ElseIf Selection.Offset(0, 1) <> "" Then
         Selection.Offset(0, 1).Select
End If
Selection.Interior.ColorIndex = 33
Loop
End Sub

[ 本帖最后由 HHAAMM 于 2008-11-7 13:00 编辑 ]

HHAAMM · 发表于 2008-11-7 12:58

原代码修改成下面这样后，再运行26楼的代码
Sub peng()
x = 1
y = 1
z = [AG1]             '长度
ReDim arr(1 To z + 100, 1 To 30)
arr(1, 1) = 1
[B1] = "A"
Cells(z + 2, 2) = "B"
For i = 1 To 2          '难度系数
      x = 1
      y = 1
      Do
         Do
            If Rnd() > 0.5 Then
                  xx = 0
                  yy = Fix(Rnd() * 20 - 10)
            Else
                  yy = 0
                  xx = Fix(Rnd() * 20 - 7)
            End If
         Loop While Not (x + xx > 0 And y + yy > 0 And y + yy < 30)
         Do
            If xx <> 0 Then x = x + xx / Abs(xx): xx = xx - xx / Abs(xx)
            If yy <> 0 Then y = y + yy / Abs(yy): yy = yy - yy / Abs(yy)
            arr(x, y) = 1
         Loop While xx + yy <> 0
      Loop While x < z
Next i
For i = 1 To y
      arr(z, i) = 1
Next
Range("a1:AE65536").Interior.ColorIndex = 0
Range(Cells(1, 1), Cells(z + 2, 1)).Interior.ColorIndex = 3
Range(Cells(1, 31), Cells(z + 1, 31)).Interior.ColorIndex = 3
Range(Cells(1, 3), Cells(1, 31)).Interior.ColorIndex = 3
Range(Cells(z + 2, 3), Cells(z + 2, 31)).Interior.ColorIndex = 3
Range(Cells(2, 2), Cells(z + 1, 31)) = arr
End Sub

lbpp · 发表于 2008-11-7 12:58

前面有人已经提到了动态规划，这个问题应该是离散数学中的图论问题（这门功能没学好），求最短路径。上次在google黑板报中看到了一篇讲述动态规划的文章，用的例子是在地图上找最短路径，由于水平有限，只能了解一个思想，但不能写出解决的代码，在此贴上那篇文章的地址http://googlechinablog.com/2008/10/blog-post_14.html，希望高手能解决这个问题，让我们也学习一下。

yuanhongly · 发表于 2008-11-7 16:28

求最短距离.rar (16.44 KB, 下载次数: 37) 自己弄了下。胡搅蛮缠 + 胡思乱想+ 文不对题+误解楼主原意

但是有点像在找路了。哈哈只看运行效果还有点像那么回事，只是偶尔会找错路

看完代码你会拿石头砸我的！！哈哈

还是等着学习高人的答案吧

[ 本帖最后由 yuanhongly 于 2008-11-7 16:58 编辑 ]

彭希仁 · 发表于 2008-11-7 18:29

原帖由 joforn 于 2008-11-7 12:43 发表
如果1->5->9可以走，那么到底是空白单元表示路径还是-1表示路径？

-1表示可以走的路径

		自动登录	找回密码
密码			免费注册

[讨论] 求A点到B点之间最短的一条路线(看谁速度最快)