পাইথনে হাউস রঙ করার ন্যূনতম খরচ বের করার প্রোগ্রাম

মান লিজিয়ে m সাইজের একটি অ্যারে আছে যা mটি বাসা রিপ্রেজেন্ট করে একটি ছোট সিটিতে। প্রতিটি বাসা অবশ্যই n রংয়ে যেকোনো একটা রঙ দিতে হবে (রংগুলো ১ থেকে n পর্যন্ত লেবেলড)। কিছু বাসা ইতিমধ্যে রঙা আছে, সেগুলো আবার রঙ দিতে হবে না। যেসব বাসা একই রঙ দিয়ে রঙা হয়েছে সেগুলোকে नेবরহুড বলা হয়। আমাদের houses অ্যারেটি আছে যেখানে houses[i] হল i-তম বাসার রঙ, যদি মান ০ হয় তবে বাসাটি এখনো রঙা নয়। আরেকটি অ্যারে আছে costs, এটি ২D অ্যারে যেখানে costs[i][j] হল i-তম বাসাকে j+1 নম্বর রঙ দিয়ে রঙ করার খরচ। আরেকটি ইনপুট আছে target। আমাদের বাকি বাসাগুলো রঙ দিয়ে এমনভাবে রঙ করতে হবে যাতে ঠিক target সংখ্যক नेবরহুড থাকে। ন্যূনতম খরচ বের করতে হবে। সমাধান না থাকলে -1 রিটার্ন করুন।

যেমন, ইনপুট হলে houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], n = 2, target = 3, তবে আউটপুট হবে 11 কারণ কিছু বাসা ইতিমধ্যে রঙা আছে, তাই আমরা বাসাগুলো এমনভাবে রঙ করব [2,2,1,2,2]। এখানে তিনটি नेবরহুড: [{2,2}, {1}, {2,2}]। প্রথম ও শেষ বাসা রঙ করার মোট খরচ (10 + 1) = 11।

সমাধানের ধাপসমূহ

m := len(houses)
helper(i, p_col, grp) ফাংশন ডিফাইন করুন।
যদি i == m হয়, তবে 0 if grp == target else inf রিটার্ন করুন।
যদি houses[i] != 0 হয়, তবে:
- helper(i+1, houses[i], grp + int(p_col != houses[i])) রিটার্ন করুন।
total := inf
col = 1 থেকে n পর্যন্ত:
- total = min(total, cost[i][col-1] + helper(i+1, col, grp + int(p_col != col)))
total রিটার্ন করুন।
মেইন মেথড থেকে:
ans := helper(0, -1, 0)
ans if ans != inf else -1 রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(houses, cost, n, target):
    m = len(houses)
    def helper(i, p_col, grp):
        if i == m:
            return 0 if grp == target else float('inf')
        if houses[i] != 0:
            return helper(i + 1, houses[i], grp + int(p_col != houses[i]))
        total = float('inf')
        for col in range(1, n + 1):
            total = min(total, cost[i][col - 1] + helper(i + 1, col, grp + int(p_col != col)))
        return total
    ans = helper(0, -1, 0)
    return ans if ans != float('inf') else -1

houses = [0,2,1,2,0]
cost = [[1,10],[10,1],[10,1],[1,10],[5,1]]
n = 2
target = 3
print(solve(houses, cost, n, target))

ইনপুট

[0,2,1,2,0], [[1,10],[10,1],[10,1],[1,10],[5,1]], 2, 3