a982迷宮問題(VB版)

   Dim n As Integer                     ' n x n 方形
    Dim a(100, 100) As Integer    '假設最大為 100x100

    Private Sub Form1_Load( ． ． ． ) Handles MyBase.Load
        FileOpen(1, "in.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)

        For fn = 1 To 1
            If fn > 1 Then PrintLine(3) ' 第2個檔 in2 與 in1 之間換行
            Dim t As Short = LineInput(fn) ' t 筆
            For k = 1 To t
                n = LineInput(fn) ' n x n  迷宮
                ' 讀入：將#轉為-1、.轉為0 => a(i,j)

                For i = 1 To n
                    Dim line = LineInput(fn) ' 讀入一行
                    For j = 1 To n
                        If (Mid(line, j, 1) = "#") Then a(i, j) = -1
                    Next j
                Next i
                Dim ans = maze(2, 2, n - 1, n - 1)
                If (ans > 0) Then
                    PrintLine(3, "" & ans)
                Else
                    PrintLine(3, "No solution!")
                End If
            Next k
        Next fn
        End
    End Sub

    Dim dy() As Integer = {-1, 1, 0, 0}  ' 上 下 左 右 的列位移(y座標)
    Dim dx() As Integer = {0, 0, -1, 1}  '               行位移(x座標)

    Function maze(ByVal sy As Integer, ByVal sx As Integer, ByVal gy As Integer, ByVal gx As Integer) As Integer   '這是接上一行

        If sy = gy And sx = gx Then  '起點
            If a(sy, sx) = 0 Then Return 1 Else Return 0
        End If
        Const MaxQ As Integer = 200  '假設 queue容量 最大為 200
        Dim qh(MaxQ) As Integer, qy(MaxQ) As Integer, qx(MaxQ) As Integer
        Dim p As Integer = 0, r As Integer = 0 '佇列的頭、尾 {若p=r為空}
        Dim h As Integer = 1, y As Integer, x As Integer
        a(sy, sx) = 1                   ' 將 起點 (sy,sx)及距離 h=1 放入 queue內 ， 並a(sy,sx)設為 h
        qh(r) = h : qy(r) = sy : qx(r) = sx : r = (r + 1) Mod MaxQ   ' (h:sy,sx)  放進 queue尾
        Do Until (p = r)   '當 queue 為空時 結束迴圈
            '取出 queue 的第1筆(頭) 資料  h , y , x
            h = qh(p) : y = qy(p) : x = qx(p) : p = (p + 1) Mod MaxQ
            For d = 0 To 3  '四個方向 找 a(ny,nx) = 0
                Dim ny As Integer = y + dy(d), nx As Integer = x + dx(d)
                If ny < 1 Or ny > n Or nx < 1 Or nx > n Then Continue For
                If a(ny, nx) = 0 Then    ' a(ny,nx)=0 ：有路可走 h+1
                    If ny = gy And nx = gx Then Return h + 1      ' 終點
                   '  將此格資訊 h+1步，ny,nx 座標放入 queue 尾
                    a(ny, nx) = h + 1
                    qh(r) = h + 1 : qy(r) = ny : qx(r) = nx : r = (r + 1) Mod MaxQ  ' (h:ny,nx)   push 進 queue
                End If
            Next
        Loop
        Return 0
    End Function

in.txt 輸入檔

2

9

#########

#.......#

#.#####.#

#.......#

##.#.####

#..#.#..#

#.##.##.#

#.......#

#########

9

#########

#.......#

#.#####.#

#.......#

##.#.####

#..#.#..#

#.#####.#

#.......#

#########

out.txt 輸出檔

13

No solution!