On this page

ข้อ 47 · LC1926 Nearest Exit from Entrance in Maze (ทางออกใกล้สุดในเขาวงกต) 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

โจทย์ถามก้าวน้อยสุด = สัญญาณ BFS เก็บ steps ไปกับพิกัดใน queue ช่องติดขอบช่องแรกคือคำตอบ

โจทย์ (LC1926): กำหนด grid (ตาราง) ขนาด m x n ชื่อ maze ที่แต่ละช่องเป็นช่องว่าง (แทนด้วย '.') หรือกำแพง (แทนด้วย '+') พร้อมตำแหน่งเริ่มต้น entrance = [entrance_row, entrance_col] ในหนึ่งก้าวสามารถเดินขึ้น ลง ซ้าย หรือขวาไปยังช่องว่างที่ติดกันได้ ห้ามเดินเข้าช่องกำแพงและห้ามเดินออกนอก grid ให้หา exit (ทางออก) ที่ใกล้ที่สุดจากทางเข้า โดย exit คือช่องว่างที่อยู่ที่ขอบของ grid (โดยทางเข้าเองไม่นับเป็น exit) ให้ return จำนวนก้าวของเส้นทางที่สั้นที่สุดจากทางเข้าไปยัง exit ที่ใกล้สุด หรือ -1 ถ้าไม่มีเส้นทางเช่นนั้น

Example 1

Input:: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Output:: 1
Explanation:: ในเขาวงกตนี้มีทางออกอยู่ 3 จุดคือ [1,0], [0,2], [2,3] ทางออกที่ใกล้สุดคือ [0,2] ซึ่งห่างจากทางเข้าแค่ 1 ก้าว

Example 2

Input:: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
Output:: 2
Explanation:: มีทางออกอยู่จุดเดียวคือ [1,2] ซึ่งห่างจากทางเข้า 2 ก้าว

Example 3

Input:: maze = [[".","+"]], entrance = [0,0]
Output:: -1
Explanation:: ในเขาวงกตนี้ไม่มีทางออกเลยแม้แต่จุดเดียว

Constraints (ข้อจำกัด)

maze.length == m และ maze[i].length == n
1 <= m, n <= 100
แต่ละช่องเป็น . (เดินได้) หรือ + (กำแพง)
ช่อง entrance เป็น . เสมอ

ทางเข้าเองไม่นับเป็นทางออก แม้จะติดขอบก็ตาม ต้องเช็คเงื่อนไขติดขอบกับช่องใหม่ที่เดินไปเท่านั้น

แนวทาง — ต้องใช้อะไร & คิดยังไง

ใช้ BFS (Breadth-First Search) บน grid เพราะโจทย์ถามจำนวนก้าว น้อยที่สุด นี่คือสัญญาณชัดเจนว่าใช้ BFS ไม่ใช่ DFS เนื่องจาก BFS แผ่ตามระยะทาง ช่องแรกที่ไปถึงและเป็น exit ย่อมเป็น exit ที่ใกล้สุดโดยอัตโนมัติ

เราเก็บจำนวนก้าวไปพร้อมกับพิกัดใน queue (คิว) เลย (r, c, steps) พอ pop (ดึง) ช่องไหนออกมาก็รู้ทันทีว่ามันห่างจากทางเข้ากี่ก้าว และเพื่อประหยัด memory เราเขียนทับช่องที่ visited (เคยเยือน) แล้วด้วย + (ทำให้มันกลายเป็นกำแพง) แทนการสร้าง set visited แยก

อ่านขนาด grid และพิกัดทางเข้า initialize (ตั้งค่าเริ่มต้น) directions 4 ทิศ
push (ใส่) (start_r, start_c, 0) ลง queue แล้วปิดช่องเริ่มด้วย + เพื่อกันเดินซ้ำ
iterate (วน) จน queue หมด pop (r, c, steps) ออกจากหัว queue
ลอง neighbor (เพื่อนบ้าน) 4 ทิศ ช่องใหม่ต้องอยู่ใน grid และเป็น . (เดินได้)
ถ้าช่องใหม่ติดขอบ return steps + 1 ทันที (นี่คือ exit ที่ใกล้สุด)
ถ้าไม่ติดขอบ ปิดช่องด้วย + แล้ว append (ต่อท้าย) (nr, nc, steps + 1) เข้า queue
ถ้าเดินจน queue หมดไม่เจอ exit return -1

จุดพลาดที่พบบ่อย

นับทางเข้าเป็น exit เพราะมันก็ติดขอบ ต้องปิดช่องเริ่มไว้ตั้งแต่ต้นและเช็คเงื่อนไขติดขอบกับช่อง ใหม่ เท่านั้น อีกจุดคือลืมทำเครื่องหมายช่องตอน push เข้า queue ทำให้ช่องเดียวถูก push ซ้ำหลายรอบ

ไล่ทีละสเต็ป

รันบน maze = [[+,+,.,+],[.,.,.,+],[+,+,+,.]], entrance = [1,2]

pop (r,c,steps)	neighbor ที่เดินได้	ผล
(1,2,0)	(0,2) เป็น . และ (1,1) เป็น .	(0,2) ติดขอบบน → return 0+1 = 1

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

from collections import deque

def nearest_exit(maze, entrance):
    rows, cols = len(maze), len(maze[0])
    start_r, start_c = entrance
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    queue = deque([(start_r, start_c, 0)])   # (แถว, คอลัมน์, จำนวนก้าว)
    maze[start_r][start_c] = "+"             # ทำเครื่องหมายว่าเยี่ยมแล้ว (ปิดทาง)

    while queue:
        r, c, steps = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # ต้องอยู่ในตาราง และเป็นทางเดินได้
            if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == ".":
                # ถ้าช่องใหม่อยู่ติดขอบ นี่คือทางออก
                if nr == 0 or nr == rows - 1 or nc == 0 or nc == cols - 1:
                    return steps + 1
                maze[nr][nc] = "+"           # ปิดทางกันเดินซ้ำ
                queue.append((nr, nc, steps + 1))
    return -1                                # เดินจนทั่วแล้วไม่เจอทางออก

maze = [["+", "+", ".", "+"],
        [".", ".", ".", "+"],
        ["+", "+", "+", "."]]
print(nearest_exit(maze, [1, 2]))            # 1

Output

เพราะโจทย์ถามจำนวนก้าว น้อยที่สุด นี่คือสัญญาณชัดเจนว่าใช้ BFS เราเก็บจำนวนก้าวไปพร้อมกับพิกัดใน queue เลย (r, c, steps) พอ pop ช่องไหนออกมาก็รู้ทันทีว่ามันห่างจากทางเข้ากี่ก้าว เมื่อเราเดินไปเจอช่องว่างที่ติดขอบเป็นครั้งแรก เพราะ BFS แผ่ตามระยะ ช่องนั้นย่อมเป็น exit ที่ใกล้สุด return steps + 1 ได้เลย

ทริกประหยัด memory คือแทนที่จะสร้าง set visited แยก เราเขียนทับช่องที่ visited แล้วด้วย + (ทำให้มันกลายเป็นกำแพง) เพื่อกันเดินซ้ำ จุดที่ต้องระวังคือทางเข้า ไม่ นับเป็น exit แม้จะติดขอบ โค้ดจึงเช็คเงื่อนไขติดขอบเฉพาะกับช่อง ใหม่ (nr, nc) ที่ไม่ใช่ช่องเริ่ม และปิดช่องเริ่มตั้งแต่ต้น

Time O(rows × cols) เยี่ยมแต่ละช่องมากสุดหนึ่งครั้ง · Space O(rows × cols) จาก queue ในกรณีแย่สุด

💡 สรุป pattern

เจอคำว่า ก้าวน้อยสุด / ระยะสั้นสุด บน grid ให้นึกถึง BFS เก็บ steps ไปกับพิกัดใน queue แล้ว return ทันทีที่เจอเป้าหมายครั้งแรก และใช้เขียนทับ grid แทน visited ได้เมื่อได้รับอนุญาตให้แก้ input