Tìm số lần di chuyển tối thiểu cần thiết để chuyển từ một ô của ma trận sang ô khác trong Python

Giả sử chúng ta có một N X N ma trận M và ma trận này chứa 1, 0, 2, 3, Chúng ta phải tìm số lần di chuyển tối thiểu cần thiết để di chuyển từ ô nguồn đến ô đích . Trong khi chỉ truy cập qua các ô trống, chúng tôi có thể truy cập lên, xuống, phải và trái.

• Ô có giá trị 1 cho biết Nguồn.

• Ô có giá trị 2 cho biết Điểm đến.

• Ô có giá trị 3 cho biết ô trống.

• Ô có giá trị 0 cho biết Tường trống.

Sẽ chỉ có một nguồn và chỉ một ô đích. Có thể có nhiều hơn một đường dẫn đến đích từ ô nguồn. Bây giờ, mỗi bước di chuyển trong ma trận chúng tôi coi là '1'.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 5,

Từ đầu đến đích, con đường xanh là ngắn nhất.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• các nút:=order * order + 2

• g:=một đồ thị trống với số đỉnh của 'nút'

• k:=1

• đối với tôi trong phạm vi 0 để đặt hàng, hãy làm

  • đối với j trong phạm vi 0 để đặt hàng, thực hiện

    • nếu mat [i, j] không giống 0 thì

      • nếu is_ok (i, j + 1, mat) khác 0 thì

        • tạo một cạnh giữa k và k + 1 nút của g

      • nếu is_ok (i, j - 1, mat) khác 0, thì

        • tạo một cạnh giữa k, k - 1 nút của g

      • nếu j

        • tạo một cạnh giữa k, k + nút thứ tự của g

      • nếu i> 0 và is_ok (i - 1, j, mat) khác 0 thì

        • tạo một cạnh giữa k, k - các nút thứ tự của g

    • nếu mat [i, j] giống 1 thì

      • src:=k

    • nếu mat [i, j] giống 2 thì

      • đích:=k

    • k:=k + 1

• trả về biểu diễn bfs từ src đến đích của g

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

0