จำนวนการเคลื่อนไหวขั้นต่ำเพื่อหนีเมทริกซ์เขาวงกตใน Python

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

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

แล้วเอาท์พุตจะเป็น 8 เพราะเราสามารถเลือกเส้นทางได้ เช่น −

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

• R :=จำนวนแถว
• C :=จำนวนคอลัมน์
• q :=รายการว่าง เริ่มแรกแทรก (0, 0, 1) ถ้า matrix[0, 0] เป็น 0
• เมทริกซ์[0, 0] :=1
• สำหรับแฝดสามแต่ละตัว (r, c, d) ใน q, do
  • ถ้า (r, c) เหมือนกับ (R - 1, C - 1) แล้ว
    • คืนสินค้า
  • สำหรับแต่ละ x, y ใน [(r + 1, c) ,(r - 1, c) ,(r, c + 1) ,(r, c - 1) ] ทำ
    • ถ้า 0 <=x
    • เมทริกซ์[x, y] :=1
    • ใส่ triplet (x, y, d + 1) ที่ส่วนท้ายของ q

ตัวอย่าง

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

defแก้ปัญหา(เมทริกซ์):R, C =len(เมทริกซ์), len(เมทริกซ์[0]) q =[(0, 0, 1)] ถ้าไม่ใช่เมทริกซ์[0][0] อื่น [] เมทริกซ์[ 0][0] =1 สำหรับ r, c, d ใน q:if (r, c) ==(R - 1, C - 1):คืนค่า d สำหรับ x, y ใน [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:ถ้า 0 <=x  
อินพุต
 <ก่อนหน้า>[[0, 0, 0, 1, 0],[0, 0, 1, 1, 0],[0, 0, 0, 1, 1],[1, 1, 0, 0, 0 ]]

ผลลัพธ์

8