|
|
发表于 2018-9-13 10:43
来自手机
|
显示全部楼层
本帖最后由 yipzx 于 2018-9-13 22:56 编辑
手机不好打字，附件也不好传，大家将就看一下。
下面是广度搜索。配合题意写复杂了一点。
result 是需要求的结果。这个结果可能不止一个，所以他是个集合。同时，我们考虑，如果第一个场景无解，我们需要将他的下一个场景加入判断，同时删除无解的第一个场景。还有一条广度搜索重要的条件，就是不能回到以前去过的场景，不然就无限循环了。这个需要好好体会一下，香老师之前有写。
没有用type数据结构，在昨天的函数的基础上直接给一个答案。不理解的地方，大家提出来即可。
Option Explicit
Public gMONKS As Long
Public gMONSTERS As Long
Sub main()
Dim result As New Dictionary
Dim key
Dim i As Long
Dim is_done As Boolean
Dim next_scene
gMONKS = 4
gMONSTERS = 4
result.Add "left-" & gMONKS & "-" & gMONSTERS, False
is_done = False
Do Until (result.Count = 0 Or is_done = True)
For Each key In result.Keys' 保证广度全遍历，一般广度搜索只求最短路径，这是此题特别的地方
If last_scene(key) = "right-0-0" Then
result(key) = True
is_done = True
End If
Next key
If Not is_done Then
For Each key In result.Keys
next_scene = get_next_scene(last_scene(key))
For i = LBound(next_scene) To UBound(next_scene)
If InStr(1, key, next_scene(i)) = 0 Then' 不能重复
result.Add key & "," & next_scene(i), False
End If
Next i
result.Remove key
Next key
End If
Loop
If result.Count = 0 Then Debug.Print "No result!"
For Each key In result.Keys
If result(key) Then
Debug.Print key
End If
Next key
End Sub
Function last_scene(key)
Dim tmp
tmp = Split(key, ",")
tmp = tmp(UBound(tmp))
last_scene = tmp
End Function
Function get_next_scene(scene)
Dim result, i As Long, j As Long, boat_location, left_bank_monks, left_bank_monsters, right_bank_monks, right_bank_monsters
result = Split(scene, "-")
boat_location = result(0)
left_bank_monks = result(1)
left_bank_monsters = result(2)
right_bank_monks = gMONKS - left_bank_monks
right_bank_monsters = gMONSTERS - left_bank_monsters
result = ""
If boat_location = "left" Then
For i = 0 To left_bank_monks
For j = 0 To left_bank_monsters
If i + j > 0 And i + j <= 2 Then
If is_monks_safe(left_bank_monks - i, left_bank_monsters - j, right_bank_monks + i, right_bank_monsters + j) Then
result = result & "right-" & left_bank_monks - i & "-" & left_bank_monsters - j & ","
End If
End If
Next j
Next i
End If
If boat_location = "right" Then
For i = 0 To right_bank_monks
For j = 0 To right_bank_monsters
If i + j > 0 And i + j <= 2 Then
If is_monks_safe(left_bank_monks + i, left_bank_monsters + j, right_bank_monks - i, right_bank_monsters - j) Then
result = result & "left-" & left_bank_monks + i & "-" & left_bank_monsters + j & ","
End If
End If
Next j
Next i
End If
result = Left(result, Len(result) - 1)
get_next_scene = Split(result, ",")
End Function
Function is_monks_safe(left_bank_monks, left_bank_monsters, right_bank_monks, right_bank_monsters)
is_monks_safe = (left_bank_monks = 0 Or left_bank_monks >= left_bank_monsters) And (right_bank_monks = 0 Or right_bank_monks >= right_bank_monsters)
End Function
|
|
楼主: 香川群子
[复制链接]
沪公网安备 31011702000001号 沪ICP备11019229号-2
楼主
