Chương trình tìm ra con đường ngắn nhất để đạt được mục tiêu bằng Python

Giả sử, chúng ta được cung cấp một lưới trong đó các ô chứa các ký hiệu khác nhau như 'X', 'O', '*' và '#' và các ký hiệu có nhiều ý nghĩa khác nhau.

• '#' là ô mục tiêu mà chúng tôi muốn đạt được.
• 'O' là một ô trống mà chúng ta có thể di chuyển qua ô mục tiêu.
• '*' là vị trí của chúng ta trong ô.
• 'X' là ô bị chặn mà chúng ta không thể đi qua.

Chúng tôi phải tìm ra số lần di chuyển cần thiết để đến ô mục tiêu từ vị trí hiện tại của chúng tôi trong lưới. Nếu không thể đạt được mục tiêu, chúng tôi trả về -1. Lưới được cung cấp làm đầu vào cho chương trình.

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

thì đầu ra sẽ là 2

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

• m:=số hàng của lưới
• n:=số cột của lưới
• đối với tôi trong phạm vi từ 0 đến m, thực hiện
  • đối với j trong phạm vi từ 0 đến n, thực hiện
    • nếu lưới [i, j] giống như "*", thì
      • ra khỏi vòng lặp
    • nếu không,
      • chuyển sang lần lặp tiếp theo
    • ra khỏi vòng lặp
• ans:=0
• queue:=một danh sách mới chứa cặp số nguyên (i, j)
• lưới [i, j]:="X"
• trong khi hàng đợi không trống, hãy thực hiện
  • ans:=ans + 1
  • newq:=một danh sách mới
  • đối với mỗi i, j trong hàng đợi, thực hiện
    • cho mỗi ii, jj in (i-1, j), (i, j-1), (i, j + 1), (i + 1, j), thực hiện
      • nếu 0 <=ii
      • nếu lưới [ii, jj] giống với "#", thì
        • trả lại ans
      • chèn ii, jj vào cuối newq
      • lưới [ii, jj]:="X"
• hàng đợi:=newq

Ví dụ

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

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

Đầu vào

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

Đầu ra

2