Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Python

Chương trình tìm khoảng cách tối thiểu cần đi để gặp tất cả mọi người trong Python

Giả sử chúng ta có một ma trận 2D có các giá trị như sau:

  • 0 đại diện cho ô trống.
  • 1 đại diện cho tường.
  • 2 đại diện cho người.

Ở đây một người có thể đi theo bốn hướng (lên, xuống, trái, phải). Chúng ta phải tìm một ô không phải tường sao cho nó tối thiểu hóa tổng khoảng cách đi lại mà mỗi người phải đi đến, và cuối cùng tìm khoảng cách đó.

Ví dụ, nếu đầu vào là:

2010
1012
0022

thì đầu ra sẽ là 7 vì điểm gặp gộ tốt nhất là góc dưới bên phải.

Để giải quyết, chúng ta thực hiện các bước sau:

  • twos := map mới, costs := map mới
  • với mỗi chỉ mục i và hàng r trong ma trận:
    • với mỗi chỉ mục j và giá trị v trong r:
      • nếu v bằng 2:
        • twos[i, j] := [i, j, 0]
        • costs[i, j] := tạo ma trận 2D kích thước bằng ma trận cho trước, điền bằng vô cực
  • với mỗi cặp khóa-giá trị (k, q) trong twos:
    • seen := tập hợp mới
    • trong khi q không rỗng:
      • (i, j, cost) := xóa phần tử đầu khỏi q
      • nếu (i, j) trong seen, tiếp tục vòng lặp tiếp theo
      • thêm (i, j) vào seen
      • costs[k][i][j] := cost
      • với mỗi (di, dj) trong ((1, 0), (-1, 0), (0, 1), (0, -1)):
        • (ni, nj) := (i + di, j + dj)
        • nếu ni, nj trong phạm vi ma trận và matrix[ni][nj] khác 1:
          • thêm (ni, nj, cost + 1) vào cuối q
  • ans := vô cực
  • với i từ 0 đến số hàng của ma trận:
    • với j từ 0 đến số cột của ma trận:
      • cur_cost := 0
      • với mỗi arr trong danh sách tất cả giá trị của costs:
        • cur_cost := cur_cost + arr[i][j]
      • ans := min(ans, cur_cost)
  • trả về ans

Ví dụ

class Solution:
    def solve(self, matrix):
        twos = {}
        costs = {}
        for i, r in enumerate(matrix):
            for j, v in enumerate(r):
                if v == 2:
                    twos[(i, j)] = [(i, j, 0)]
                    costs[(i, j)] = [[1e9 for _ in matrix[0]] for _ in matrix]
        for k, q in twos.items():
            seen = set()
            while q:
                i, j, cost = q.pop(0)
                if (i, j) in seen:
                    continue
                seen.add((i, j))
                costs[k][i][j] = cost
                for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    ni, nj = i + di, j + dj
                    if (ni >= 0 and nj >= 0 and ni < len(matrix) and nj < len(matrix[0]) and matrix[ni][nj] != 1):
                        q.append((ni, nj, cost + 1))
        ans = 1e9
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                cur_cost = 0
                for arr in costs.values():
                    cur_cost += arr[i][j]
                ans = min(ans, cur_cost)
        return ans

ob = Solution()
matrix = [
    [2, 0, 1, 0],
    [1, 0, 1, 2],
    [0, 0, 2, 2]
]
print(ob.solve(matrix))

Input

matrix = [ [2, 0, 1, 0], [1, 0, 1, 2], [0, 0, 2, 2] ]

Output

7