Giả sử chúng ta có đồ thị có hướng, với các nút có nhãn 0, 1, ..., n-1. Trong biểu đồ này, mỗi cạnh được tô màu đỏ hoặc xanh lam và có thể có các cạnh tự hoặc các cạnh song song. Mỗi [i, j] trong red_edges chỉ ra một cạnh có hướng màu đỏ từ nút i đến nút j. Tương tự, mỗi [i, j] trong blue_edges chỉ ra một cạnh có hướng màu xanh lam từ nút i đến nút j. Chúng ta phải tìm một câu trả lời mảng có độ dài n, trong đó mỗi câu trả lời [X] là độ dài của đường đi ngắn nhất từ nút 0 đến nút X sao cho các màu cạnh xen kẽ dọc theo đường dẫn (hoặc -1 nếu đường dẫn như vậy không tồn tại).
Vì vậy, nếu đầu vào là n =3, red_edges =[[0,1], [1,2]] và blue_edges =[], thì đầu ra sẽ là [0, 1, -1]
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -
-
Xác định một phương thức gọi là bfs (), phương thức này sẽ nhận re, be, f và n
-
xác định một tập hợp được gọi là đã thăm, xác định một hàng đợi và chèn một bộ ba [0, f, 0]
-
trong khi q không trống
-
đặt ba dòng điện, màu sắc, bước là q [0] và xóa khỏi q
-
color:=bổ sung cho giá trị của màu (đúng thành sai và ngược lại)
-
res [current]:=phút của res [hiện tại] và bước
-
nếu màu khác 0 thì
-
cho mỗi tôi trong [hiện tại]
-
nếu cặp (i, màu) không được truy cập, thì chèn (i, màu) vào đã truy cập và chèn [i, color, step + 1] vào q
-
-
-
ngược lại khi màu bằng 0 thì
-
cho mỗi tôi [hiện tại]
-
nếu cặp (i, màu) không được truy cập, thì chèn (i, màu) vào đã truy cập và chèn [i, color, step + 1] vào q
-
-
-
-
Trong phương thức chính -
-
res:=một mảng các giá trị vô cực và kích thước của nó là n
-
re và be:=mảng trong số n mảng trống
-
cho mỗi phần tử i trong r:insert i [1] into re [i [0]]
-
cho mỗi phần tử i trong b:insert i [1] to be [i [0]]
-
gọi bfs (re, be, false, n) và gọi bfs (re, be, true, n)
-
cho tôi trong phạm vi từ 0 đến độ dài của res - 1
-
nếu res [i] =inf, thì res [i]:=-1
-
-
trả lại res
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution (object):def shortAlternatingPaths (self, n, r, b):self.res =[float ("inf")] * n re =[[] for i in range (n)] be =[[] for i in range (n)] for i in r:re [i [0]]. append (i [1]) for i in b:be [i [0]]. append (i [1] ) self.bfs (re, be, False, n) self.bfs (re, be, True, n) for i in range (len (self.res)):if self.res [i] ==float (' inf '):self.res [i] =- 1 return self.res def bfs (self, re, be, f, n):visit =set () queue =[[0, f, 0]] while queue:current, color, step =queue [0] queue.pop (0) color =not color self.res [current] =min (self.res [current], step) if color:for i in re [current]:nếu (i, color) not in visit:visit.add ((i, color)) queue.append ([i, color, step + 1]) elif not color:for i in be [current]:if (i, color ) không được thăm:đã thăm.add ((i, col hoặc)) queue.append ([i, color, step + 1]) ob =Solution () print (ob.shortestAlternatingPaths (3, [[0,1], [1,2]], [])) Đầu vào
3 [[0,1], [1,2]] []
Đầu ra
[0,1, -1]