โปรแกรมค้นหาจำนวนเซลล์ขั้นต่ำที่ต้องใช้เพื่อไปถึงมุมล่างขวาใน Python

สมมติว่าเรามีตาราง 2D ที่แสดงเขาวงกตโดยที่ 0 คือพื้นที่ว่าง และ 1 คือกำแพง เราจะเริ่มที่ grid[0, 0] เราต้องหาจำนวนช่องสี่เหลี่ยมขั้นต่ำที่ต้องใช้เพื่อไปที่มุมล่างขวาของตาราง หากเราไม่สามารถไปถึงได้ ให้กลับ -1

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

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

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

• R :=จำนวนแถวของตาราง C :=จำนวนคอลัมน์ของกริด

• q :=[0, 0, 1] เมื่อ A[0, 0] เป็น 1 มิฉะนั้นจะเป็นรายการใหม่

• A[0, 0] :=1

• สำหรับแต่ละ (r, c, d) ใน q ทำ

  • ถ้า (r, c) เหมือนกับ (R -1, C -1) แล้ว

    • กลับ d

  • 
    

    • สำหรับแต่ละ (x, y) ใน [(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1) ] ทำ

      • ถ้า x ในช่วง 0 ถึง R และ y ในช่วง 0 ถึง C และ A[x, y] เท่ากับ 0 ดังนั้น

        • A[x, y] :=1

        • แทรก (x, y, d + 1) ที่ส่วนท้ายของ q

• กลับ -1

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

ตัวอย่าง

class Solution:
   def solve(self, A):
      R, C = len(A), len(A[0])
      q = [(0, 0, 1)] if not A[0][0] else []
      A[0][0] = 1
      for r, c, d in q:
         if (r, c) == (R − 1, C − 1):
            return d
         for x, y in [(r + 1, c), (r − 1, c), (r, c + 1), (r, c −1)]:
            if 0 <= x < R and 0 <= y < C and A[x][y] == 0:
               A[x][y] = 1
               q.append((x, y, d + 1))
      return −1
ob = Solution()
grid = [
   [0, 0, 0],
   [1, 0, 0],
   [1, 0, 0]
]
print(ob.solve(grid))

อินพุต

grid = [ [0, 0, 0], [1, 0, 0], [1, 0, 0] ]

ผลลัพธ์

5