2012年10月1日 星期一

100正式Problem 2-1：二維陣列的應用

子題 1：(程式執行限制時間: 3 秒) 12 分
有一長及寬均是 15 公分的正方形地圖，其長及寬各以1 公分為長度畫分為15 個小單位，而地圖內共有225 個單位。在這些單位中，有的已被填色，有的是空白。被「填色」的單位代表其「不可通過」，而「空白」的單位則「可通行」。假設地圖上「最左上角」及「最右下角」分別代表「起點」及「終點」，起、迄兩點一定是「空白」，請問從起點到終點，在最多只能通過若干個空白單位的限制條件下，是否有可通行的路徑？(任一單位只能透過上、下、
左、右四個方向連到下一單位。)
輸入說明：
第 1 行是最多能通過的空白單位數目（不包括起點及終點）。
第 2~16 行是第1 張地圖的資料，依序代表地圖上的每個橫列。每行有15 個符號，依序代表
地圖上每個橫列的15 個小單位。若符號為「0」，表示該單位為「空白」；若為「1」，表示已「填色」。
第 17 行為空行。
接著另有 15 行資料，代表第2 張地圖，其表示方式和第1 張地圖相同。
輸出說明：
第 1、2 行是輸入檔案1 的檢查結果。
第 1 行輸出第1 張地圖在條件限制下是否有可通行的路徑，若有則輸出「TRUE」，沒有則輸
出「FALSE」。
第 2 行輸出第2 張地圖的檢查結果，其值是「TRUE」或「FALSE」。
第 3 行是空白。
第 4、5 行是輸入檔案2 的檢查結果。
第 4 行輸出第1 張地圖的檢查結果，其值是「TRUE」或「FALSE」。
第 5 行輸出第2 張地圖的檢查結果，其值是「TRUE」或「FALSE」。
（輸出均為大寫，選手請注意。）
輸入檔案 1：【檔名：in1.txt】
40
011111110010000
000000000010000
000001000010000
000001000010000
000001000010000
111101000010000
000001011000000
000001000000000
100001000011111
100000000000000
100111111111110
100000000000000
100000000001000
100000000001000
100000000001000

011111110010000
000000000010000
000001000010000
000001000011110
000001000010010
111110100010100
000001011000100
000001001000100
100001001011111
100000001000000
100111111111111
100000100110000
100000100001000
100000000001000
100000000001000
輸入檔案 2：【檔名：in2.txt】
40
000000000000111
100011111110000
100010000000000
111110000000000
100000000000000
100010111111111
100010000000000
100010001111000
101010001001000
101110001001000
100000001001000
111111111001000
000000000001000
000000000001000
000000000000110

010000000000000
010000000111100
010000000100100
000000000100100
111111111100100
000001000000100
000001001000100
000001001000100
000001001000100
000001001000000
000001001111111
000001000100000
000001000100000
000001000100000
000000000000000

輸出檔案：【檔名：out.txt】
TRUE
FALSE

TRUE
FALSE
張貼者： 於

3 則留言:

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

    Dim k(16, 16), m As Integer
    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\IN1.TXT" For Input As #1
    Open App.Path & "\in2.txt" For Input As #2
    Open App.Path & "\out.txt" For Output As #3
    For k1 = 1 To 2
    Input #k1, m
    For L = 1 To 2
    For i = 1 To 15
    Line Input #k1, x
    For j = 1 To 15
    k(i, j) = Mid(x, j, 1)
    Next
    If i = 15 And L <> 2 Then Input #k1, x
    Next
    Call abc
    Next
    Print #3,
    Next
    Close
    Close
    End
    End Sub
    Sub abc()
    '洪水演算法
    n = 4
    k(1, 1) = 5
    Do Until Val(k(15, 15)) <> 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(15, 15) = 0 Or k(15, 15) > (m + 6) Then Print #3, "False": Exit Sub
    If k(15, 15) <> 0 And k(15, 15) <= (m + 6) Then Print #3, "TRUE"
    End Sub

    回覆刪除
  2. 吾存在2012年10月3日 下午1:48

    Dim s(15, 15)
    Private Sub Form_Load()
    Form1.Show
    For i = 1 To 2
    Open App.Path & "\in" & i & ".txt" For Input As #1
    Input #1, indata
    For asd = 1 To 2
    For X = 1 To 15
    Line Input #1, nn
    For Y = 1 To 15
    s(X, Y) = Val(Mid(nn, Y, 1))
    Next
    Next
    Call R(1, 1, 2)
    If s(15, 15) = 0 Then
    ch = "FALSE"
    Else
    If Val(s(15, 15) - 3) <= Val(indata) Then
    ch = "TRUE"
    Else
    ch = "FALSE"
    End If
    End If
    Print ch
    If asd = 1 Then Line Input #1, nn
    Next
    Print
    Close #1
    Next

    End Sub

    Function R(ByVal X, ByVal Y, ByVal lenR)
    s(X, Y) = lenR
    If X > 1 Then
    If s(X - 1, Y) = 0 Or lenR + 1 < s(X - 1, Y) Then
    Call R(X - 1, Y, lenR + 1)
    End If
    End If

    If Y > 1 Then
    If s(X, Y - 1) = 0 Or lenR + 1 < s(X, Y - 1) Then
    Call R(X, Y - 1, lenR + 1)
    End If
    End If

    If X < 15 Then
    If s(X + 1, Y) = 0 Or lenR + 1 < s(X + 1, Y) Then
    Call R(X + 1, Y, lenR + 1)
    End If
    End If

    If Y < 15 Then
    If s(X, Y + 1) = 0 Or lenR + 1 < s(X, Y + 1) Then
    Call R(X, Y + 1, lenR + 1)
    End If
    End If
    End Function

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

    Dim k(16, 16), m As Integer
    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\IN1.TXT" For Input As #1
    Open App.Path & "\in2.txt" For Input As #2
    Open App.Path & "\out.txt" For Output As #3
    For k1 = 1 To 2
    Input #k1, m
    m = m + 6
    For L = 1 To 2
    For i = 1 To 15
    Line Input #k1, x
    For j = 1 To 15
    k(i, j) = Mid(x, j, 1)
    Next
    If i = 15 And L <> 2 Then Input #k1, x
    Next
    List1.Clear
    Call abc
    Next
    Print #3,
    Next
    Close
    Close
    End
    End Sub
    Sub abc()
    n = 4
    k(X1, Y1) = 5
    Do Until k(15, 15) <> 0 Or n = 230
    n = n + 1
    List1.AddItem 1 & " " & 1
    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 And k(i, 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(15, 15) = 0 Or m < k(15, 15) Then Print #3, "FALSE"
    If k(15, 15) <> 0 And m >= k(15, 15) Then Print #3, "TRUE"
    End Sub

    回覆刪除

訂閱： 張貼留言 (Atom)