Tìm khoảng cách ngắn nhất từ ​​người bảo vệ bằng Bankin Python

Giả sử chúng ta có một ma trận chứa ba chữ cái 'O', 'G' và 'W' trong đó 'O' đại diện cho không gian mở, 'G' đại diện cho các lính canh và 'W' đại diện cho các bức tường trong ngân hàng, chúng ta phải thay thế tất cả các chữ O trong ma trận theo khoảng cách ngắn nhất của chúng với một người bảo vệ, chúng ta không thể đi qua bất kỳ bức tường nào. Trong các bộ bảo vệ ma trận đầu ra được thay thế bằng 0 và các bức tường được thay thế bằng -1.

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

thì đầu ra sẽ là

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

• M:=5

• N:=5

• dir_row:=[-1, 0, 1, 0]

• dir_col:=[0, 1, 0, -1]

• Định nghĩa một hàm is_ok (). Điều này sẽ mất tôi, j

• nếu (i trong phạm vi 0 và M) hoặc (j trong phạm vi 0 và j N), thì

  • trả về Sai

• trả về True

• Xác định một hàm isSafe (). Điều này sẽ lấy i, j, ma trận, kết quả

• nếu ma trận [i, j] không phải là 'O' hoặc kết quả [i, j] không phải là -1, thì

  • trả về Sai

• trả về True

• Xác định một hàm allow_dist (). Điều này sẽ sử dụng ma trận

• result:=tạo ma trận có thứ tự M x N và điền vào -1

• Xác định hàng đợi kết thúc kép q

• đối với tôi trong phạm vi từ 0 đến M, hãy thực hiện

  • đối với j trong phạm vi từ 0 đến N, thực hiện

    • kết quả [i, j]:=-1

    • nếu ma trận [i, j] giống với 'G' thì

      • pos:=[i, j, 0]

      • chèn vị trí ở bên trái của q

      • kết quả [i, j]:=0

• trong khi kích thước của q> 0 là khác 0, thực hiện

  • curr:=xóa phần tử cuối cùng khỏi q

  • x, y, dist:=curr [0], curr [1], curr [2]

  • đối với tôi trong phạm vi từ 0 đến 3, hãy thực hiện

    • nếu is_ok (x + dir_row [i], y + dir_col [i]) khác 0 và isSafe (x + dir_row [i], y + dir_col [i], ma trận, kết quả) khác 0, thì

      • kết quả [x + dir_row [i], y + dir_col [i]]:=dist + 1

      • pos:=[x + dir_row [i], y + dir_col [i], dist + 1]

      • chèn vị trí ở bên trái của q

• đối với tôi trong phạm vi từ 0 đến M, hãy thực hiện

  • đối với j trong phạm vi từ 0 đến N, thực hiện

    • kết quả hiển thị [i, j]

  • chuyển đến dòng tiếp theo

Ví dụ

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

from collections import deque as queue
M = 5
N = 5
dir_row = [-1, 0, 1, 0]
dir_col = [0, 1, 0, -1]
def is_ok(i, j):
   if ((i < 0 or i > M - 1) or (j < 0 or j > N - 1)):
      return False
   return True
def isSafe(i, j,matrix, result):
   if (matrix[i][j] != 'O' or result[i][j] != -1):
      return False
   return True
def calculate_dist(matrix):
   result = [[ -1 for i in range(N)]for i in range(M)]
   q = queue()
   for i in range(M):
      for j in range(N):
         result[i][j] = -1
         if (matrix[i][j] == 'G'):
            pos = [i, j, 0]
            q.appendleft(pos)
            result[i][j] = 0
   while (len(q) > 0):
      curr = q.pop()
      x, y, dist = curr[0], curr[1], curr[2]
   for i in range(4):
      if is_ok(x + dir_row[i], y + dir_col[i]) and isSafe(x + dir_row[i], y + dir_col[i], matrix, result) : result[x + dir_row[i]][y + dir_col[i]] = dist + 1
      pos = [x + dir_row[i], y + dir_col[i], dist + 1]
      q.appendleft(pos)
   for i in range(M):
      for j in range(N):
         if result[i][j] > 0:
            print(result[i][j], end=" ")
         else:
            print(result[i][j],end=" ")
      print()

matrix = [['O', 'O', 'O', 'O', 'G'],
   ['O', 'O', 'O', 'W', 'O'],
   ['O', 'W', 'O', 'O', 'O'],
   ['G', 'W', 'W', 'W', 'O'],
   ['O', 'O', 'O', 'O', 'G']]

calculate_dist(matrix)

Đầu vào

[['O', 'O', 'O', 'O', 'G'],
['O', 'O', 'O', 'W', 'O'],
['O', 'W', 'O', 'O', 'O'],
['G', 'W', 'W', 'W', 'O'],
['O', 'O', 'O', 'O', 'G']]

Đầu ra

3 3 2 1 0
2 3 3 -1 1
1 -1 4 3 2
0 -1 -1 -1 1
1 2 2 1 0