Chương trình tìm số bước tối thiểu để tất cả người gặp nhau tại một ô trong Python

Giả sử ta có ma trận 2D với các giá trị: 0 là ô trống, 1 là tường, 2 là người. Người có thể đi 4 hướng (lên, xuống, trái, phải) hoặc đứng yên trong 1 đơn vị thời gian. Ta phải tìm ô đi được sao cho thời gian tối đa để mọi người gặp nhau là nhỏ nhất, trả về thời gian đó. Hai người có thể đi qua cùng ô trống, và luôn có đường đi giữa hai người bất kỳ.

Ví dụ:

Đầu ra = 2, vì tất cả có thể gặp tại matrix[1,1] trong tối đa 2 bước.

Để giải quyết, ta làm theo các bước:

• Định nghĩa hàm bfs(r, c).
• queue := hàng đợi chứa (r,c).
• dist := map {(r,c):0}.
• for mỗi (r,c) trong queue:
  • Nếu dist[r,c] > 15: break.
  • for mỗi hàng xóm (nr,nc) của (r,c):
    • Nếu (nr,nc) chưa trong dist: dist[nr,nc] = dist[r,c]+1; thêm vào queue.
• Trả về dist.
• Từ main:
  • dist := null.
  • for mỗi hàng r, row của A:
    • for mỗi cột c, giá trị val của row[c]:
      • Nếu val == 2: ndist = bfs(r,c); nếu dist là null: dist = ndist; ngược lại: for key trong dist.keys(): nếu key trong ndist: dist[key] = max(dist[key], ndist[key]); ngược lại: xóa dist[key].
  • Trả về min của tất cả giá trị dist nếu dist không rỗng, ngược lại 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