2012年10月2日 星期二

100模擬Problem 2-2：二維陣列的應用


子題 2：假設地圖上的每個小單位都有一個（x, y）座標，其中x 代表該單位的橫座標，y 代表縱座標。地圖上「最左上角」的小單位其座標值是（1, 1），該橫列第15 個小單位其座標值是（1, 15）；第15 個橫列的第1 個小單位是（15, 1），該橫列最後1 個小單位是（15, 15）。
如果我們任意給定地圖上「起點」及「終點」的座標，在地圖上此兩點均為「空白」，請問從起點到終點是否有可通行的路徑？
輸入說明：
前15 行是地圖的資料，依序代表地圖上的每個橫列。每行有15 個符號，依序代表地圖上每
個橫列的15 個小單位。若符號為「0」，表示該單位為「空白」；若為「1」，表示已「填色」。
第16 行為空行。
第17、18 行是檢測第1 組資料。
第17 行是「起點座標」，第1 個數字是起點的x 座標，空格後接著「y 座標」。
第18 行是「終點座標」，第1 個數字是終點的x 座標，空格後接著「y 座標」。
第19 行為空行。
第20、21 行是檢測第2 組資料。
第20 行是「起點座標」，第1 個數字是起點的x 座標，空格後接著「y 座標」。
第21 行是「終點座標」，第1 個數字是終點的x 座標，空格後接著「y 座標」。
輸出說明：
第1 行輸出第1 組檢測資料是否有可通行的路徑。若有則輸出「TRUE」，沒有則輸出「FALSE」。
第2 行輸出第2 組檢測資料的檢查結果，同樣是「TRUE」或「FALSE」。
（輸出均為大寫，選手請注意。）
輸入範例：【檔名：in-2-2.txt】
011111110010000
000000000010000
000001000010000
000001000011110
000001000010010
111110100010100
000001011000100
000001001000100
100001001011111
100000001000000
100111111111111
100000100110000
100000100001000
100000000001000
100000000001000

3 3
5 13

14 11
2 14
輸出範例：【檔名：out-2-2.txt】
TRUE
FALSE
張貼者： 於

4 則留言:

  1. 匿名2012年10月2日 晚上10:07

    Dim k(16, 16) As Integer
    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\IN2-2.TXT" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    For i = 1 To 15
    Line Input #1, x
    For j = 1 To 15
    k(i, j) = Mid(x, j, 1)
    Next
    Next
    For i = 1 To 2
    Input #1, m
    Input #1, x1, y1
    Input #1, x2, y2
    Call abc(x1, y1, x2, y2)
    Next
    Close
    Close
    End
    End Sub
    Sub abc(x1, y1, x2, y2)
    '洪水演算法
    n = 4
    k(x1, y1) = 5
    Do Until k(x2, y2) <> 0 Or n = 230
    n = n + 1
    For i = 1 To 15
    For j = 1 To 15
    If Val(k(i, j)) = n Then
    If k(i, j - 1) = 0 Then k(i, j - 1) = n + 1
    If k(i + 1, j) = 0 Then k(i + 1, j) = n + 1
    If k(i, j + 1) = 0 Then k(i, j + 1) = n + 1
    If k(i - 1, j) = 0 Then k(i - 1, j) = n + 1
    End If
    Next
    Next
    Loop
    If k(x2, y2) = 0 Then Print #2, "False": Exit Sub
    If k(x2, y2) <> 0 Then Print #2, "TRUE"
    End Sub

    回覆刪除
  2. 匿名2012年10月8日 下午2:45

    Dim l(15)
    Dim a(15, 15)
    Dim f1, f2
    Dim t As Boolean
    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\in-2-2.txt" For Input As #1
    Open App.Path & "\out-2-1.txt" For Output As #2
    For i = 1 To 15
    Line Input #1, s
    For j = 1 To 15
    a(i, j) = Mid(s, j, 1)
    Next j
    Next i
    Line Input #1, s
    Input #1, s1, s2, f1, f2
    t = False
    Call check(s1, s2)
    Print #2, UCase(t)
    Line Input #1, s
    Input #1, s1, s2, f1, f2
    t = False
    Call check(s1, s2)
    Print #2, UCase(t)
    Close #2
    Close #1
    End
    End Sub
    Sub check(ByVal x, ByVal y)
    If (x = f1 And y = f2) And a(x, y) = "0" Then t = True
    If x < f1 Then If a(x + 1, y) = "0" Then a(x, y) = "1": Call check(x + 1, y)
    If y < f2 Then If a(x, y + 1) = "0" Then a(x, y + 1) = "1": Call check(x, y + 1)
    If x > 1 Then If a(x - 1, y) = "0" Then a(x - 1, y) = "1": Call check(x - 1, y)
    If y > 1 Then If a(x, y - 1) = "0" Then a(x, y - 1) = "1": Call check(x, y - 1)
    End Sub

    回覆刪除
  3. 匿名2012年10月10日 下午3:39

    Dim k(16, 16) As Integer
    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\IN2-2.TXT" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    For i = 1 To 15
    Line Input #1, x
    For j = 1 To 15
    k(i, j) = Mid(x, j, 1)
    Next
    Next
    For i = 1 To 2
    Input #1, m
    Input #1, x1, y1
    Input #1, x2, y2
    For i1 = 1 To 15
    For j1 = 1 To 15
    If k(i1, j1) >= 5 Then k(i1, j1) = 0
    Next
    Next
    Call abc(x1, y1, x2, y2)
    Next
    Close
    Close
    End
    End Sub
    Sub abc(x1, y1, x2, y2)
    n = 4
    k(x1, y1) = 5
    Do Until k(x2, y2) <> 0 Or n = 230
    n = n + 1
    List1.AddItem x1 & " " & y1
    For L = 0 To (List1.ListCount - 1)
    a = Split(List1.List(L))
    i = a(0): j = a(1)
    If i <= 15 And i >= 1 And j <= 15 And j >= 1 Then
    If k(i, j - 1) = 0 Then k(i, j - 1) = n + 1: List2.AddItem i & " " & j - 1
    If k(i + 1, j) = 0 Then k(i + 1, j) = n + 1: List2.AddItem i + 1 & " " & j
    If k(i, j + 1) = 0 Then k(i, j + 1) = n + 1: List2.AddItem i & " " & j + 1
    If k(i - 1, j) = 0 Then k(i - 1, j) = n + 1: List2.AddItem i - 1 & " " & j
    End If
    Next
    List1.Clear
    For L = 0 To (List2.ListCount - 1)
    List1.AddItem List2.List(L)
    Next
    List2.Clear
    Loop
    If k(x2, y2) = 0 Then Print #2, "FALSE": Exit Sub
    If k(x2, y2) <> 0 Then Print #2, "TRUE"
    End Sub

    回覆刪除
  4. 匿名2012年10月13日 晚上11:23

    Dim k(16, 16) As Integer
    Dim ans As String
    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\IN2-2.TXT" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    For i = 1 To 15
    Line Input #1, x
    For j = 1 To 15
    k(i, j) = Mid(x, j, 1)
    Next
    Next
    For i = 1 To 2
    If i = 1 Then Input #1, m
    Input #1, x1, y1
    Input #1, x2, y2
    k(x1, y1) = 4
    ans = "FALSE"
    Call abc(x1, y1, 4, x2, y2)
    Print #2, ans
    Next
    Close
    Close
    End
    End Sub
    Function abc(ByVal x1, ByVal y1, n, ByVal x2, ByVal y2)
    If k(x2, y2) <> 0 Then ans = "TRUE"
    If x1 >= 1 And y1 >= 1 And x1 <= 15 And y1 <= 15 Then
    If k(x1 + 1, y1) = 0 Then k(x1 + 1, y1) = n: Call abc(x1 + 1, y1, n + 1, x2, y2)
    If k(x1, y1 + 1) = 0 Then k(x1, y1 + 1) = n: Call abc(x1, y1 + 1, n + 1, x2, y2)
    If k(x1, y1 - 1) = 0 Then k(x1, y1 - 1) = n: Call abc(x1, y1 - 1, n + 1, x2, y2)
    If k(x1 - 1, y1) = 0 Then k(x1 - 1, y1) = n: Call abc(x1 - 1, y1, n + 1, x2, y2)
    End If
    End Function

    回覆刪除

訂閱： 張貼留言 (Atom)