পাইথনে অল্টারনেটিং কালারের সাথে শর্টেস্ট পাথ

মনে করুন একটি ডিরেক্টেড গ্রাফ আছে, নোডগুলো লেবেল করা ০, ১, ..., n-1। এই গ্রাফে প্রতিটি এজ বা লাল নীল রঙের। সেলফ-এজ বা প্যারালল এজ থাকতে পারে। red_edges-এ প্রতিটি [i, j] নির্দেশ করে নোড i থেকে নোড j-এ একটি লাল ডিরেক্টেড এজ। একইভাবে blue_edges-এ প্রতিটি [i, j] নির্দেশ করে নোড i থেকে নোড j-এ একটি নীল ডিরেক্টেড এজ। আমাদের একটি answer অ্যারে বের করতে হবে লেন্থ n, যেখানে প্রতিটি answer[X] হলো নোড ০ থেকে নোড X-এ শর্টেস্ট পাথের লেন্থ যাতে এজ কালারগুলো পাথ boyunca অল্টারনেট করে (অথবা -1 যদি এমন পাথ না থাকে)।

ইনপুট যদি হয় n = 3, red_edges = [[0,1],[1,2]] এবং blue_edges = [], তবে আউটপুট হবে [0, 1, -1]।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (BFS):

bfs(re, be, f, n) মেথড ডিফাইন করুন:
- visited সেট, queue বানান এবং [0, f, 0] ইনসার্ট করুন।
- while q not empty
  - current, color, step = q.pop(0)
  - color := not color (টগল)
  - res[current] := min(res[current], step)
  - যদি color true হয় (লাল), তবে re[current]-এর প্রতিটি i জন্য, যদি (i, color) ভিজিটেড না হয়, তবে ভিজিটেডে যোগ করুন এবং [i, color, step+1] কিউতে পুশ করুন।
  - অন্যথায় (নীল), be[current]-এর প্রতিটি i জন্য একই কাজ করুন।
মেইন মেথড:
- res := infinity অ্যারে, size n
- re, be := n খালি অ্যারে
- red_edges থেকে re এবং blue_edges থেকে be বানান।
- bfs(re, be, False, n) এবং bfs(re, be, True, n) কল করুন।
- res-এ inf থাকলে -1 সেট করুন।
- return res

উদাহরণ (Python)

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।

class Solution(object):
    def shortestAlternatingPaths(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):
        visited = 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]:
                    if (i, color) not in visited:
                        visited.add((i, color))
                        queue.append([i, color, step+1])
            elif not color:
                for i in be[current]:
                    if (i, color) not in visited:
                        visited.add((i, color))
                        queue.append([i, color, step+1])

ob = Solution()
print(ob.shortestAlternatingPaths(3, [[0,1], [1,2]], []))

ইনপুট

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

আউটপুট

[0, 1, -1]