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

สมมติว่าเรามีเมทริกซ์ N X N หนึ่งตัว และนี่เต็มไปด้วย 1, 0, 2, 3 เราต้องหาจำนวนการเคลื่อนไหวขั้นต่ำที่จำเป็นในการย้ายจากเซลล์ต้นทางไปยังเซลล์ปลายทาง . ขณะที่เข้าชมผ่านช่องเปล่าเท่านั้น เราสามารถขึ้น ลง ขวา และซ้ายได้

• เซลล์ที่มีค่า 1 หมายถึง Source.

• เซลล์ที่มีค่า 2 หมายถึงปลายทาง

• เซลล์ที่มีค่า 3 หมายถึงเซลล์ว่าง

• เซลล์ที่มีค่า 0 หมายถึง Blank Wall.

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

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

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

จากจุดเริ่มต้นไปยังปลายทาง เส้นทางสีเขียวจะสั้นที่สุด

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

• โหนด :=สั่งซื้อ * สั่งซื้อ + 2

• g :=กราฟเปล่าที่มีจำนวนจุดยอด 'โหนด'

• k :=1

• สำหรับผมอยู่ในช่วง 0 สั่งทำ

  • สำหรับ j ในช่วง 0 สั่งทำ

    • ถ้า mat[i, j] ไม่เหมือนกับ 0 แล้ว

      • ถ้า is_ok (i , j + 1 , mat) ไม่ใช่ศูนย์ ดังนั้น

        • สร้างขอบระหว่าง k และ k + 1 โหนดของ g

      • ถ้า is_ok (i , j - 1 , mat) ไม่ใช่ศูนย์ ดังนั้น

        • สร้างขอบระหว่าง k, k - 1 โหนดของ g

      • ถ้า j

        • สร้างขอบระหว่าง k, k + โหนดลำดับของ g

      • ถ้า i> 0 และ is_ok (i - 1 , j , mat) ไม่ใช่ศูนย์ ดังนั้น

        • สร้างขอบระหว่าง k, k - โหนดลำดับของ g

    • ถ้า mat[i, j] เหมือนกับ 1 แล้ว

      • src :=k

    • ถ้า mat[i, j] เหมือนกับ 2 แล้ว

      • ปลายทาง :=k

    • k :=k + 1

• กลับมาดำเนินการ bfs จาก src ไปยังปลายทางของ g

ตัวอย่าง

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

class Graph:
   def __init__(self, nodes):
      self.nodes = nodes
      self.adj = [[] for i in range(nodes)]
   def insert_edge (self, src , dest):
      self.adj[src].append(dest)
      self.adj[dest].append(src)
   def BFS(self, src, dest):
      if (src == dest):
         return 0
      level = [-1] * self.nodes
      queue = []
      level[src] = 0
      queue.append(src)
      while (len(queue) != 0):
         src = queue.pop()
            i = 0
            while i < len(self.adj[src]):
               if (level[self.adj[src][i]] < 0 or level[self.adj[src][i]] > level[src] + 1 ):
level[self.adj[src][i]] = level[src] + 1 queue.append(self.adj[src][i])
               i += 1
      return level[dest]

def is_ok(i, j, mat):
   global order
   if ((i < 0 or i >= order) or (j < 0 or j >= order ) or mat[i][j] == 0):
      return False
   return True
def get_min_math(mat):
   global order
   src , dest = None, None
   nodes = order * order + 2
   g = Graph(nodes)
   k = 1
   for i in range(order):
      for j in range(order):
         if (mat[i][j] != 0):
            if (is_ok (i , j + 1 , mat)):
               g.insert_edge (k , k + 1)
            if (is_ok (i , j - 1 , mat)):
               g.insert_edge (k , k - 1)
            if (j < order - 1 and is_ok (i + 1 , j , mat)):
               g.insert_edge (k , k + order)
            if (i > 0 and is_ok (i - 1 , j , mat)):
               g.insert_edge (k , k - order)
         if(mat[i][j] == 1):
            src = k
         if (mat[i][j] == 2):
            dest = k
         k += 1
   return g.BFS (src, dest)
order = 4
mat = [[3,3,1,0], [3,0,3,3], [3,3,0,3], [0,3,2,3]]
print(get_min_math(mat))

อินพุต

[[3,3,1,0], [3,0,3,3], [3,3,0,3], [0,3,2,3]]

ผลลัพธ์

0