|
|
下面的内容在网上找的 希望对各位有帮助，，，我只想早点看到答案啊...
迷宫最短路径问题
求两点路径是一个数据结构上的典型的迷宫问题，很多数据结构的书上都有介绍，解决办法如下：从一点开始出发，向四个方向查找，每走一步，把走过的点的值-1(即本节点值+1)，防止重复行走，并把走过的点压入堆栈(表示路径)，如果遇到墙、或者已走过的点则不能前进……
-1表示路，空白表示墙，求其中任意两点的最短路径。
求两点路径是一个数据结构上的典型的迷宫问题.
从一点开始出发，向四个方向查找，每走一步，把走过的点的值+1(即本节点值+1)，防止重复行走，并把走过的点压入堆栈(表示路径)，如果遇到墙、或者已走过的点则不能前进，如果前方已经无路可走，则返回，路径退栈，这样递归调用，直到找到终点为止。
如果我们调整调用offset的顺序，即先左右，后上下，可能会得到更短的路径，但无法确保在任何情况下都能得到最短路径。
得到最短路径的方法：
每走一步，就对前方的节点赋值为此节点+1，走过的路径也可以重复行走。这样走遍所有的节点，记录最短的路径。
‘迷宫数据，存于文本文件
11 11 '迷宫规模
0 0 10 11 '入口和出口
-1 0 0 1 1 0 0 -1
1 0 0 1 1 1 1 1 1 0 0 1
1 1 0 1 1 0 0 1 1 0 0 1
1 1 1 0 1 0 1 1 1 1 1 1
0 0 1 1 1 0 1 0 1 0 0 1
1 1 1 1 0 1 1 0 1 0 0 1
1 1 0 1 0 1 0 1 1 0 0 1
1 1 1 1 1 1 0 1 1 1 1 1
0 1 0 0 1 0 0 0 1 0 1 0
1 1 1 1 1 1 1 1 0 0 1 0
1 0 0 1 0 1 0 1 1 0 1 0
1 1 1 0 1 1 0 1 1 1 1 1
0 0 1 1 1 1 1 1 1 0 0 0
Private Type TNode
Rows As Integer
Cols As Integer
Last As Integer
End Type
Dim State() As TNode
Dim Rows As Integer, Cols As Integer
Dim Goal As TNode
Dim Maze() As Integer
Dim Rep() As Boolean
Dim dx(3) As Integer, dy(3) As Integer
Private Sub Form_Resize()
With txtS
.Top = 0
.Left = 0
.Height = ScaleHeight
.Width = ScaleWidth
End With
End Sub
Private Sub InputData()
Dim FName As String
Dim i As Integer
With CommonDialog1
.Filter = "(*.txt)|*.txt"
.ShowOpen
FName = .FileName
End With
Open FName For Input As #1
Input #1, Rows, Cols
Input #1, State(0).Rows, State(0).Cols
Input #1, Goal.Rows, Goal.Cols
ReDim Maze(Rows, Cols)
For i = 0 To 3
Input #1, dx(i), dy(i)
Next
For i = 0 To Rows
For j = 0 To Cols
Input #1, Maze(i, j)
Next
Next
Close
ReDim Rep(Rows, Cols)
End Sub
Private Function Moves(Temp As TNode, ByVal i As Integer) As Boolean
With Temp
If .Rows + dx(i) >= 0 And .Rows + dx(i) <= Rows And _
.Cols + dy(i) >= 0 And .Cols + dy(i) <= Cols Then
If Maze(.Rows + dx(i), .Cols + dy(i)) = 1 Then
.Rows = .Rows + dx(i)
.Cols = .Cols + dy(i)
Moves = True
End If
End If
End With
End Function
Private Sub PrintPath(State() As TNode, ByVal Tail As Integer)
If Tail > 0 Then
Tail = State(Tail).Last
PrintPath State, Tail
txtS = txtS & State(Tail).Rows & " " & State(Tail).Cols & vbCrLf
End If
End Sub
Private Sub BFS()
Dim Temp As TNode
Dim Head As Integer, Tail As Integer
InputData
Head = 0
Tail = 0
Do While Head <= Tail
For i = 0 To 3
Temp = State(Head)
If Moves(Temp, i) Then
If Not Rep(Temp.Rows, Temp.Cols) Then
Rep(Temp.Rows, Temp.Cols) = True
Tail = Tail + 1
ReDim Preserve State(Tail)
State(Tail) = Temp
State(Tail).Last = Head
If Temp.Rows = Goal.Rows And Temp.Cols = Goal.Cols Then
Tail = Tail + 1
ReDim Preserve State(Tail)
State(Tail).Last = Tail - 1
PrintPath State, Tail
Exit Sub
End If
End If
End If
Next
Head = Head + 1
Loop
End Sub
Private Sub DFS()
Dim Temp As TNode
Dim Head As Integer
InputData
Head = 0
Do While Head >= 0
For i = 0 To 3
Temp = State(Head)
If Moves(Temp, i) Then
If Not Rep(Temp.Rows, Temp.Cols) Then
Rep(Temp.Rows, Temp.Cols) = True
Head = Head + 1
ReDim Preserve State(Head)
State(Head) = Temp
State(Head).Last = Head - 1
txtS = txtS & State(Head).Rows & " " & State(Head).Cols & vbCrLf
If Temp.Rows = Goal.Rows And Temp.Cols = Goal.Cols Then Exit Sub
i = 0
End If
End If
Next
Head = Head - 1
Loop
End Sub
Private Sub mnuBFS_Click()
ReDim State(0)
BFS
End Sub
Private Sub mnuDFS_Click()
ReDim State(0)
DFS
End Sub
Private Sub mnuOpen_Click()
mnuBFS_Click
End Sub
Private Sub mnuSave_Click()
Dim FName As String
Dim i As Integer
With CommonDialog1
.Filter = "(*.txt)|*.txt"
.ShowSave
FName = .FileName
End With
Open FName For Append As #1
Print #1, vbCrLf
Print #1, txtS
Close
End Sub |
|
楼主: 彭希仁
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2008-11-8 02:57
楼主
称之为灌水法确实形象
