Computer >> Máy Tính >  >> Lập trình >> C ++

Chương trình tìm số bước tối thiểu cần thiết để gặp tất cả mọi người tại bất kỳ ô nào bằng Python

Giả sử chúng ta có một ma trận 2D trong đó các giá trị này hiện diện:0 đại diện cho một ô trống. 1 đại diện cho một bức tường. 2 đại diện cho một người. Bây giờ một người có thể đi bất kỳ hướng nào trong bốn hướng lên, xuống, trái, phải nếu không thì ở trong một đơn vị thời gian. Chúng ta phải tìm một phòng giam có thể đi lại được sao cho giảm thiểu thời gian mọi người gặp nhau và trả lại thời gian. Chúng ta phải lưu ý rằng hai người có thể đi qua cùng một ô trống và bạn có thể cho rằng luôn có một con đường nào đó giữa hai người bất kỳ.

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

2 0 1 0
1 0 0 2
2 0 2 0

thì đầu ra sẽ là 2, vì tất cả đều có thể gặp nhau tại ma trận vị trí [1, 1] với nhiều nhất 2 bước.

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

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

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

  • queue:=xác định hàng đợi và chèn một cặp (r, c) vào đó

  • dist:=một bản đồ với cặp giá trị khóa {(r, c):0}

  • đối với mỗi cặp (r, c) trong hàng đợi, thực hiện

    • nếu dist [r, c]> 15 khác 0 thì

      • đi ra từ vòng lặp

    • đối với mỗi hàng xóm (nr, nc) của (r, c), thực hiện

      • nếu (nr, nc) không có trong dist, thì

        • dist [nr, nc]:=dist [r, c] + 1

        • insert (nr, nc) vào cuối hàng đợi

    • trả lại bản phân phối

  • Từ phương thức chính, thực hiện như sau -

  • dist:=null

  • đối với mỗi số hàng r và các phần tử hàng tương ứng của A, thực hiện

    • đối với mỗi số cột c và giá trị của hàng [c] val, thực hiện

      • nếu val bằng 2 thì

        • ndist:=bfs (r, c)

        • nếu dist là null, thì

          • dist:=ndist

        • nếu không,

          • cho mỗi khóa trong các khóa của dist, do

            • nếu khóa nằm trong ndist, thì

              • dist [key]:=tối đa dist [key], ndist [key]

            • nếu không,

              • loại bỏ dist [key]

  • trả về giá trị tối thiểu của tất cả các giá trị của dist nếu dist không trống, nếu không trả về 0

Ví dụ 

class Solution:
def solve(self, A):
   R, C = len(A), len(A[0])
   def get_neighbor(r, c):
      for nr, nc in ((r − 1, c), (r, c − 1), (r + 1, c), (r, c + 1)):
         if 0 <= nr < R and 0 <= nc < C and A[nr][nc] & 1 == 0:
            yield nr, nc
      def bfs(r, c):
         queue = [(r, c)]
         dist = {(r, c): 0}
         for r, c in queue:
            if dist[r, c] > 15:
               break
            for nr, nc in get_neighbor(r, c):
               if (nr, nc) not in dist:
                  dist[nr, nc] = dist[r, c] + 1
                  queue.append((nr, nc))
         return dist
      dist = None
      for r, row in enumerate(A):
         for c, val in enumerate(row):
            if val == 2:
               ndist = bfs(r, c)
               if dist is None:
                  dist = ndist
               else:
                  for key in list(dist.keys()):
                     if key in ndist:
                        dist[key] = max(dist[key],ndist[key])
                     else:
                        del dist[key]
      return min(dist.values()) if dist else 0
ob = Solution()
matrix = [
   [2, 0, 1, 0],
   [1, 0, 0, 2],
   [2, 0, 2, 0]
]
print(ob.solve(matrix))

Đầu vào 

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

Đầu ra 

2