[Visual Basic 6.0] 解迷宮路徑利用深度優先搜尋 (DFS,Depth-First-Search)

2013-11-13

摘要:[Visual Basic 6.0] 解迷宮路徑利用深度優先搜尋 (DFS,Depth-First-Search)

# Input Maze

# Output Maze


(0,0) (0,1) (1,1) (2,1) (3,1) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (5,6) (5,7) (6,7) (7,7)

利用 DFS 深度優先搜尋來找尋可以從 0,0 走到 7,7 的路徑 (請使用程式概念左上角為 0,0 右下角為 7,7 看)


Dim Maze() ' MazeRoute
Private Sub Form_Activate()
    Open App.Path & "/In.txt" For Input As #1
    Open App.Path & "/Out.txt" For Output As #2
    
    ReDim Maze(7, 7) ' add MazeRoute
    
    Do While Not EOF(1) ' 讀入迷宮
        For I = 0 To 7
                Line Input #1, Inp
            For J = 0 To 7
                Maze(I, J) = Mid(Inp, J + 1, 1) ' 0 (可走訪未走訪) 1 (不可走訪)
            Next J
        Next I
    Loop
    
    Call SearchMazeRoute(0, 0, "") ' Call SearchMazeRoute Function
    Close ' 關閉
    End ' 結束
End Sub

Function SearchMazeRoute(X, Y, RouteTemp) ' 深度優先搜尋 (DFS,Depth-First-Search)
    If X >= 0 And X <= 7 And Y >= 0 And Y <= 7 Then ' 不超出迷宮
        If X = 7 And Y = 7 Then
            Print #2, RouteTemp & "(" & Y & "," & X & ") " ' 找到答案後輸出
        ElseIf Val(Maze(X, Y)) = 0 Then
            Maze(X, Y) = "2" ' 已走訪
            Call SearchMazeRoute(X + 1, Y, RouteTemp & "(" & Y & "," & X & ") ") ' 走訪下一格
            Call SearchMazeRoute(X - 1, Y, RouteTemp & "(" & Y & "," & X & ") ") ' 走訪下一格
            Call SearchMazeRoute(X, Y + 1, RouteTemp & "(" & Y & "," & X & ") ") ' 走訪下一格
            Call SearchMazeRoute(X, Y - 1, RouteTemp & "(" & Y & "," & X & ") ") ' 走訪下一格
            ' (上下左右都跑過 RouteTemp 為記錄走訪路徑)
        End If
    End If
End Function

[Visual Baisc 6.0] 利用 DFS 搜尋迷宮路徑.rar

#0xDe 從分享中學習

#Facebook：ProgrammerDe (https://www.facebook.com/MicrosoftDes) 有問題歡迎提問

回首頁