[Visual Basic 6.0] 解陷阱利用廣度優先搜尋法 (BFS,Breadth-First-Search)

2013-11-05

摘要:[Visual Basic 6.0] 解陷阱利用廣度優先搜尋法 (BFS,Breadth-First-Search)

B.陷阱

Time Limit:1000MS  Memory Limit:65536K
Total Submit:78 Accepted:43

Description

　　身為一個考古學家，勇氣和運氣是不可或缺的成功因素，在古老的國度裡，充斥著現代文明無法理解的謎。有些時候這些謎團讓我們贊嘆先人的成就，但更多機會我們落入古老的詛咒，得費盡心思逃解開謎題，避免成為下一具不知名的枯骨。

　　考古學家小光在一次埃及歴險的過程中，闖入了一個未曾有人到過的密室，透過牆上的小孔看去，他發現了牆壁後無數的金銀珠寶。正當苦苦思索如何前進的同時，牆壁上一個怪異的突起吸引了他的注意。這個形狀像按鈕的突起恰好位在一個5x5方陣的正中央，旁邊並以古埃及文刻了一串訊息：

XXXXX
XXXXX
XXOXX
XXXXX
XXXXX
「讓二十五位忠心的英靈安息吧！」

　　好奇心驅使他按下了這個按鈕，沒想到就在這個突起被壓下的同時，周圍的四個按鈕卻浮了起來：

XXXXX
XXOXX
XOXOX
XXOXX
XXXXX
　　他又按了右上角已被壓下的按鈕，結果三個按鈕一起浮了起來：

XXXOO
XXOXO
XOXOX
XXOXX
XXXXX

　　經過試驗小光證實了無論按哪一個按鈕，也無論這個按鈕一開始是壓下或是浮上，都將造成按鈕本身和上下左右相鄰按鈕狀態的改變，他有理由相信只要壓下所有按鈕，通往寶藏的秘室之門就會開啟，然而就在此時，兩側的牆壁竟無聲無息地靠了上來，他沒有多少時間了！在他成為陷阱裡的下一個亡魂之前，請你以最快的速度幫助小光讓所有英靈安息吧！

Input

輸入包含數筆測試資料，每筆測試資料均為一由O和X組成的矩陣，至多六行，每行至多六個字元。O表示目前突起的按鈕，X則表示已壓下的，你的目標是將所有按鈕壓下。兩筆測試資料之間以一個空白行分隔，最後一筆資料之後會有一行空白和一個'#'表示結束。

Output

對每一筆測試資料，使用以下格式輸出一行表示完成所需的最小按鈕次數：

Minimum Steps : n

n表示所需最小按鈕次數。如果無論如何無法達成目標，則輸出一行：

Another Skeleton in the Ancient Tomb!

注意：倘若同一按鈕前後被按兩次，應計為兩個按鈕次數。

Sample Input

OO
OO

XOX
OOO
XOX

OX

#

Sample Output

Minimum Steps : 4
Minimum Steps : 1
Another Skeleton in the Ancient Tomb!

# http://218.210.35.237:8080/JudgeOnline/showproblem?problem_id=1046

這一題當我看到題目時想到的就是廣度優先搜尋法 (BFS,Breadth-First-Search) ，雖然可能有更好的解法，但解最佳解、最佳路徑，就是 BFS 準沒錯！

演算法：

(1) 判斷目前是否已經是答案 ( 是則跳出 )

            If InStr(TempNows, "O") = 0 Then
                Outs = Outs & "Minimum Steps : " & 步數 & vbCrLf
                Exit Sub
            End If

(2) 紀錄目前狀態 => 將此次狀態列出所有下一次狀態可能 => 恢復狀態

Sub BFS()
    ' BFS (每個都按一次)
    For I = 1 To X
        For J = 1 To Y
            GoTemp ' 紀錄
            Call Change(I, J)  ' 交煥
            
            
            ' 判斷現況是否重複 沒重複繼續
            ' 現在 = TempNows
            TempNows = ""
            For I1 = 1 To X
                For J1 = 1 To Y
                    TempNows = TempNows & XY(I1, J1)
                Next J1
            Next I1
            
            If InStr(TempNows, "O") = 0 Then
                Outs = Outs & "Minimum Steps : " & B & vbCrLf
                Me.Tag = "Over"
                Exit Sub
            End If
                S = True
            For I1 = 0 To K
                If ArrayTemp(I1) = TempNows Then S = False
            Next I1
            
            If S Then
                ArrayTemp(K) = TempNows
                K = K + 1
            End If
                
            RGoTemp ' 恢復
        Next J
    Next I
End Sub

Sub Change(I, J)
    If I >= 1 And I <= X And J >= 1 And J <= Y Then
        If XY(I, J) = "X" Then
            XY(I, J) = "O"
        Else
            XY(I, J) = "X"
        End If
            ' 自己跟周圍相反
            Call Change2(I + 1, J)
            Call Change2(I - 1, J)
            Call Change2(I, J + 1)
            Call Change2(I, J - 1)
    End If
End Sub

Sub Change2(I, J)
    If I >= 1 And I <= X And J >= 1 And J <= Y Then
        If XY(I, J) = "X" Then
            XY(I, J) = "O"
        Else
            XY(I, J) = "X"
        End If
    End If
End Sub

Sub GoTemp() ' 紀錄
    For I = 1 To X
        For J = 1 To Y
            TempXY(I, J) = XY(I, J)
        Next J
    Next I
End Sub

Sub RGoTemp() ' 恢復
    For I = 1 To X
        For J = 1 To Y
            XY(I, J) = TempXY(I, J)
        Next J
    Next I
End Sub

Sub RGoTempNow(K) ' 恢復新的
        S = 1
    For I = 1 To X
        For J = 1 To Y
            XY(I, J) = Mid(ArrayTemp(K), S, 1)
            S = S + 1
        Next J
    Next I
End Sub

※ 記得要將跑過 BFS 的狀態設成某值，才不會造成重複判斷來增加延遲時間。

然後我自己建立的測試資料：

XOOO
XXXO
XXXO
OOOX

OO
OO

XOX
OOO
XOX

OX

OX
XO

XOO
XXX
XOO

OXXX
XOOX
XOXO
XXOO

XOXXX
OXOOX
OXXOO
XOXOX
XXXXX

#

Minimum Steps : 5
Minimum Steps : 4
Minimum Steps : 1
Another Skeleton in the Ancient Tomb ! 
Minimum Steps : 2
Minimum Steps : 2
Minimum Steps : 3
Minimum Steps : 3

#0xDe 從分享中學習

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

回首頁