โปรแกรมค้นหาเส้นทางที่สั้นที่สุดเพื่อไปให้ถึงเป้าหมายใน Python

สมมติว่าเราได้รับตารางที่เซลล์มีสัญลักษณ์ต่างๆ เช่น 'X', 'O', '*' และ '#' และสัญลักษณ์มีความหมายต่างๆ

• '#' คือเซลล์เป้าหมายที่เราต้องการไปให้ถึง
• 'O' เป็นช่องว่างที่เราสามารถเดินทางไปยังเซลล์เป้าหมายได้
• '*' คือตำแหน่งของเราในเซลล์
• 'X' คือเซลล์ที่ถูกปิดกั้น ซึ่งเราไม่สามารถเดินทางได้

เราต้องหาจำนวนการเคลื่อนไหวที่จำเป็นในการเข้าถึงเซลล์เป้าหมายจากตำแหน่งปัจจุบันของเราในตาราง หากไม่สามารถบรรลุเป้าหมายได้ เราจะคืนค่า -1 กริดจะถูกกำหนดให้เป็นอินพุตของโปรแกรม

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• m :=จำนวนแถวของตาราง
• n :=จำนวนคอลัมน์ของกริด
• สำหรับฉันในช่วง 0 ถึง m ให้ทำ
  • สำหรับ j ในช่วง 0 ถึง n ทำ
    • ถ้า grid[i, j] เหมือนกับ "*" แล้ว
      • ออกมาจากวงจร
    • มิฉะนั้น
      • ติดตามตอนต่อไป
    • ออกมาจากวงจร
• ตอบ :=0
• queue :=รายการใหม่ที่มีคู่จำนวนเต็ม (i, j)
• grid[i, j] :="X"
• ขณะที่คิวไม่ว่างให้ทำ
  • อัน :=ans + 1
  • newq :=รายการใหม่
  • สำหรับแต่ละ i, j ในคิว, ทำ
    • สำหรับแต่ละ ii, jj in(i-1, j) ,(i, j-1) ,(i, j+1) ,(i+1, j), do
      • ถ้า 0 <=ii
      • ถ้า grid[ii, jj] เหมือนกับ "#" แล้ว
        • คืนสินค้า
      • ใส่ ii, jj ต่อท้าย newq
      • grid[ii, jj] :="X"
• คิว :=newq

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(grid):
   m, n = len(grid), len(grid[0])
   for i in range(m):
      for j in range(n):
         if grid[i][j] == "*": break
      else: continue
      break
   ans = 0
   queue = [(i, j)]
   grid[i][j] = "X"
   while queue:
      ans += 1
      newq = []
      for i, j in queue:
         for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
            if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] != "X":
               if grid[ii][jj] == "#": return ans
               newq.append((ii, jj))
               grid[ii][jj] = "X"
      queue = newq
   return -1

print(solve([['X', 'X', 'O', 'X'],['X', 'X', '*', 'X'],['X', '#',
'O', 'X'],['X', 'X', 'X', 'X']]))

อินพุต

[['X', 'X', 'O', 'X'],
['X', 'X', '*', 'X'],
['X', '#', 'O', 'X'],
['X', 'X', 'X', 'X']]

ผลลัพธ์

2