Giả sử chúng ta có một ma trận 2D có vài giá trị như dưới đây -
-
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.
Ở đây một người có thể đi bất kỳ trong bốn hướng này (lên, xuống, trái và phải). Chúng ta phải tìm một ô không phải là tường sao cho nó giảm thiểu tổng quãng đường di chuyển mà mỗi người phải đi bộ đến và cuối cùng là tìm được khoảng cách.
Vì vậy, nếu đầu vào giống như
| 2 | 0 | 1 | 0 |
| 1 | 0 | 1 | 2 |
| 0 | 0 | 2 | 2 |
thì đầu ra sẽ là 7 vì điểm gặp gỡ tốt nhất là góc dưới cùng bên phải.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
twos:=một bản đồ mới, chi phí:=một bản đồ mới
-
đối với mỗi chỉ mục i và hàng r trong ma trận, thực hiện
-
đối với mỗi chỉ số j và giá trị v trong r, thực hiện
-
nếu v giống 2 thì
-
twos [i, j]:=[i, j, 0]
-
Cost [i, j]:=tạo ma trận 2D có kích thước như ma trận đã cho và điền vào vô cùng
-
-
-
-
đối với mỗi cặp giá trị khóa (k, q) trong hai thứ, hãy thực hiện
-
đã thấy:=một tập hợp mới
-
trong khi q không trống, thực hiện
-
(i, j, cost):=phần tử đầu tiên bị xóa khỏi q
-
nếu (i, j) được nhìn thấy, thì
-
chuyển sang lần lặp tiếp theo
-
-
thêm (i, j) vào đã thấy
-
chi phí [k, i, j]:=chi phí
-
cho mỗi (di, dj) trong ((1, 0), (−1, 0), (0, 1), (0, −1)), thực hiện
-
(ni, nj):=(i + di, j + dj)
-
nếu ni và nj nằm trong phạm vi của ma trận và ma trận [ni, nj] không phải là 1 thì
-
insert (ni, nj, cost + 1) vào cuối q
-
-
-
-
-
ans:=infinity
-
đối với tôi trong phạm vi 0 đến số hàng của ma trận, hãy thực hiện
-
đối với j trong phạm vi 0 đến số cột của ma trận, thực hiện
-
cur_cost:=0
-
đối với mỗi arr trong danh sách tất cả các giá trị của chi phí, hãy thực hiện
-
cur_cost:=cur_cost + arr [i, j]
-
-
ans:=tối thiểu ans và cur_cost
-
-
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Giải pháp:def giải (tự, ma trận):twos ={} Cost ={} cho i, r trong liệt kê (ma trận):cho j, v trong liệt kê (r):if v ==2:twos [ (i, j)] =[(i, j, 0)] chi phí [(i, j)] =[[1e9 cho _ trong ma trận [0]] cho ma trận _in] cho k, q trong twos.items () :saw =set () while q:i, j, cost =q.pop (0) if (i, j) in saw:continue saw.add ((i, j)) cost [k] [i] [j ] =chi phí cho di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):ni, nj =i + di, j + dj if (ni> =0 và nj> =0 và ni Đầu vào
matrix =[[2, 0, 1, 0], [1, 0, 1, 2], [0, 0, 2, 2]]
Đầu ra
7