2012年10月1日 星期一
100模擬Problem 2-1：二維陣列的應用
子題1：有一長及寬均是15 公分的正方形地圖，其長及寬各以1 公分為長度畫分為15 個小單
位，因此地圖內共有225 個單位。在這些單位中，有的已被填色，有的是空白。被「填色」
的單位代表其「不可通過」，而「空白」的單位則「可通行」。假設地圖上「最左上角」及「最左下角」分別代表「起點」及「終點」，起、迄兩點一定是「空白」，請選手判斷從起點到終點是否有可通行的路徑？（路徑沒有方向性，每個空白單位也不限制經過幾次。）
輸入說明：
前15 行是第1 張地圖的資料，依序代表地圖上的每個橫列。每行有15 個符號，依序代表地
圖上每個橫列的15 個小單位。若符號為「0」，表示該單位為「空白」；若為「1」，表示已「填色」。
第16 行為空行。
接著另有15 行地圖的資料，代表第2 張地圖的資料，其表示法和第1 張地圖相同。
輸出說明：
第1 行輸出第1 張地圖在起、迄兩點間是否有可通行的路徑？若有則輸出「TRUE」，沒有則
輸出「FALSE」。
第2 行輸出第2 張地圖的檢查結果，同樣是「TRUE」或「FALSE」。
（輸出均為大寫，選手請注意。）
輸入範例：【檔名：in-2-1.txt】
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
輸出範例：【檔名：out-2-1.txt】
TRUE
FALSE
訂閱：
張貼留言 (Atom)
Dim k(16, 16) As Integer
回覆刪除Private Sub Form_Load()
Me.Hide
Open App.Path & "\IN2-1.TXT" For Input As #1
Open App.Path & "\out.txt" For Output As #2
For L = 1 To 2
For i = 1 To 15
Line Input #1, x
For j = 1 To 15
k(i, j) = Mid(x, j, 1)
Next
If i = 15 And L <> 2 Then Input #1, x
Next
Call abc
Next
Close
Close
End
End Sub
Sub abc()
'洪水演算法
n = 4
k(1, 1) = 5
Do Until 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 Then Print #2, "False": Exit Sub
If k(15, 15) <> 0 Then Print #2, "TRUE"
End Sub
Dim s(15, 15)
回覆刪除Dim chk
Private Sub Form_Load()
Form1.Show
Open App.Path & "\in-2-1.txt" For Input As #1
For i = 1 To 2
For x = 1 To 15
Line Input #1, n
For y = 1 To 15
s(x, y) = Mid(n, y, 1)
Next
Next
chk = False
Call r(1, 1, 15, 15)
If chk Then
Print "TRUE"
Else
Print "FALSE"
End If
If i = 1 Then Line Input #1, n
Next
End Sub
Function r(ByVal x, ByVal y, ByVal x2, ByVal y2)
If s(x2, y2) = "1" Then chk = True
If chk = True And (x = 15 And y = 15) Then Exit Function
If x < 15 Then If s(x + 1, y) <> "1" Then s(x, y) = "1": Call r(x + 1, y, x2, y2)
If y < 15 Then If s(x, y + 1) <> "1" Then s(x, y) = "1": Call r(x, y + 1, x2, y2)
If x > 1 Then If s(x - 1, y) <> "1" Then s(x, y) = "1": Call r(x - 1, y, x2, y2)
If y > 1 Then If s(x, y - 1) <> "1" Then s(x, y) = "1": Call r(x, y - 1, x2, y2)
End Function
Dim l(15)
回覆刪除Dim a(15, 15)
Dim t As Boolean
Private Sub Form_Load()
Me.Hide
Open App.Path & "\in-2-1.txt" For Input As #1
Open App.Path & "\out-2-1.txt" For Output As #2
For ii = 1 To 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
If ii = 1 Then Line Input #1, s
t = False
Call check(1, 1)
Print #2, UCase(t)
Next ii
Close #2
Close #1
End
End Sub
Sub check(ByVal x, ByVal y)
If (x = 15 And y = 15) And a(x, y) = "0" Then t = True
If x < 15 Then If a(x + 1, y) = "0" Then a(x, y) = "1": Call check(x + 1, y)
If y < 15 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
這樣應該就可以少跑很多次了。
回覆刪除Dim k(16, 16) As Integer
Private Sub Form_Load()
Me.Hide
Open App.Path & "\IN2-1.TXT" For Input As #1
Open App.Path & "\out.txt" For Output As #2
For L = 1 To 2
For i = 1 To 15
Line Input #1, x
For j = 1 To 15
k(i, j) = Mid(x, j, 1)
Next
If i = 15 And L <> 2 Then Input #1, x
Next
List1.Clear
Call abc
Next
Close
Close
End
End Sub
Sub abc()
'洪水演算法
n = 4
k(1, 1) = 5
List1.AddItem "1 1"
Do Until k(15, 15) <> 0 Or n = 230
n = n + 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 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 Then Print #2, "FALSE": Exit Sub
If k(15, 15) <> 0 Then Print #2, "TRUE"
End Sub
Dim k(16, 16) As Integer
回覆刪除Dim ans As String
Private Sub Form_Load()
Me.Hide
Open App.Path & "\IN2-1.TXT" For Input As #1
Open App.Path & "\out.txt" For Output As #2
For L = 1 To 2
For i = 1 To 15
Line Input #1, x
For j = 1 To 15
k(i, j) = Mid(x, j, 1)
Next
If i = 15 And L <> 2 Then Input #1, x
Next
k(1, 1) = 4
ans = "FALSE"
Call abc(1, 1, 4)
Print #2, ans
Next
Close
Close
End
End Sub
Function abc(ByVal x1, ByVal y1, n)
If k(15, 15) <> 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)
If k(x1, y1 + 1) = 0 Then k(x1, y1 + 1) = n: Call abc(x1, y1 + 1, n + 1)
If k(x1, y1 - 1) = 0 Then k(x1, y1 - 1) = n: Call abc(x1, y1 - 1, n + 1)
If k(x1 - 1, y1) = 0 Then k(x1 - 1, y1) = n: Call abc(x1 - 1, y1, n + 1)
End If
End Function