chakrit

อันนี้แปะไว้ให้ต่ออ่าน เอาเป็นโจทย์ Lab ข้อกลางๆ แล้วกัน เดี๋ยวจะคิดข้อยาก และข้อง่ายให้อีก รวมเป็น 3 ข้อ หรือว่าใครอยากลองทำดูก็ได้ครับ ถ้าเขียนด้วย Turbo C++ จะต้องเสียเวลาเขียน Queue ก่อนก็เลยเขียนด้วย VB.NET แทนซึ่งคิดว่า Algorithm คงจะพอเข้าใจได้ไม่ยาก แม้ว่าอาจจะเป็นภาษาที่ไม่ค่อยคุ้นหูคุ้นตาสำหรับหลายๆ คน ลองอ่านดูแล้วกันครับ

โจทย์มีอยู่ว่า กำหนด Input ให้เป็นแผนที่เขาวงกต มีจุดเริ่มต้น และทางออกบอกไว้ให้ ให้คำนวณหาระยะทางที่สั้นที่สุดจากจุดเริ่มต้นไปยังทางออก โดยสองบรรทัดแรกใน Input File เป็นความกว้างและความสูงของแผนที่ตามลำดับ สองบรรทัดถัดมาเป็นค่า X และ Y ของจุดเริ่มต้น และบรรทัดที่เหลือเป็นข้อมูลแผนที่โดย 0 คือช่องว่าง 1 คือกำแพง และ 2 คือทางออก

วิธีทำก็คือสร้าง Queue ขึ้นมา 1 อัน แล้วใส่จุดเริ่มต้นลงไป กำหนดค่าระยะทางเดินให้เป็น 0 ก้าว จากนั้นค่อยดึงๆ จุดออกมาจาก Queue เรื่อยๆ ทีละจุด นำมาประมวลผล

จากจุดที่ดึงออกมานั้นก็คำนวณระยะทางไปยังจุดข้างเคียง (นั่นคือเพิ่มจากเดิมอีก 1 ก้าว) พร้อมกับตรวจสอบว่าระยะทางจาดจุกที่กำลังประมวลผลนี้ กับระยะทางเดิมที่เคยคำนวณไว้ ณ จุดนั้น อันไหนมันน้อยกว่า ถ้าระยะทางที่คำนวณใหม่นั้นมีค่าน้อยกว่า ก็ใส่ระยะทางนั้นลงไป แล้วก็ใส่จุดนั้นลงไปใน Queue เพื่อทำการคำนวณต่อ ทำอย่างนี้ไปเรื่อยๆ จนกว่าจะเจอทางออก ระยะทางที่สั้นที่สุดจากจุดเริ่มค้นก็คือค่าระยะทางที่คำนวณได้ ณ จุดทางออกนั่นเอง

เฉลยที่ทำไว้ให้คำนวณแค่ระยะทางน่ะนะ แล้วก็ Assume ว่าทางออกสามารถไปถึงได้ แผนที่นั้นมีกำแพงล้อมรอบเสมอ และจุดเริ่มต้นจะเริ่มบนช่องว่างเท่านั้น

input.txt

10
10
8
8
1111111111
1200110101
1010100101
1010101001
1000001011
1110100011
1000101001
1011001011
1000011001
1111111111

Output

Loading input data ...
Calculating shortest path ...
Shortest path is 14 steps.

maze_exit.vb

Option Strict On
Imports System.IO
Imports System.Collections.Generic

Module modMain

    Enum MapCell As Integer
        BLANK = 0
        WALL = 1
        [EXIT] = 2
    End Enum

    Sub Main()

        Dim width, height As Integer
        Dim map As MapCell(,)
        Dim calc As Integer(,)
        Dim I%, J%
        Dim q As Queue(Of Point)
        Dim p As Point
        Dim length As Integer
        Dim shortestLength As Integer

        Console.WriteLine("Loading input data ...")

        ' open c:input.txt for reading
        ' wraps in a using block to auto-clean
        Using sr As New StreamReader("C:input.txt")

            ' read and parse map info
            width = CInt(sr.ReadLine())
            height = CInt(sr.ReadLine())
            p.X = CInt(sr.ReadLine()) 'starting point
            p.Y = CInt(sr.ReadLine())

            ' creates buffer
            map = New MapCell(width - 1, height - 1) {}
            calc = New Integer(width - 1, height - 1) {}

            ' read map data line by line
            ' and init calculation matrix with maximums
            Dim line As String
            For I = 0 To height - 1
                line = sr.ReadLine()
                For J = 0 To line.Length - 1
                    map(J, I) = CType(Integer.Parse(line.Chars(J)), MapCell)
                    calc(J, I) = Integer.MaxValue
                Next
            Next

        End Using

        Console.WriteLine("Calculating shortest path ...")

        ' initialize calculation algorithm
        q = New Queue(Of Point)()   ' queue for breadth-search
        q.Enqueue(p)                ' queue first point to calc
        calc(p.X, p.Y) = 0          ' set steps at starting point to 0

        ' while there are points left
        While q.Count > 0

            p = q.Dequeue()                         ' get a point from queue
            If map(p.X, p.Y) = MapCell.EXIT Then    ' check if is at exit
                shortestLength = calc(p.X, p.Y)     ' if so, save the length
                Exit While                          ' and exit loop
            End If

            ' if not, push surrounding points into the stack
            ' and update their walk length
            Dim pa As Point() = New Point() { _
                New Point(p.X - 1, p.Y), _
                New Point(p.X + 1, p.Y), _
                New Point(p.X, p.Y - 1), _
                New Point(p.X, p.Y + 1)}

            length = calc(p.X, p.Y) + 1             ' +1 step

            For Each p In pa
                ' do not process walls
                If map(p.X, p.Y) = MapCell.WALL Then Continue For
                If length < calc(p.X, p.Y) Then     ' if new path is shorter
                    calc(p.X, p.Y) = length         ' save new path length
                    q.Enqueue(p)                    ' enqueue point for further calc
                End If                              ' else just leave the point alone
            Next
        End While

        ' display result and halt for keypress
        Console.WriteLine("Shortest path is " + shortestLength.ToString + " steps.")
        While (Not Console.KeyAvailable) : End While

    End Sub

End Module