পাইথনে k সংখ্যক রঙ দিয়ে ফেন্স রঙ করার ন্যূনতম খরচ বের করার প্রোগ্রাম

মনে করুন আমাদের N সংখ্যক ফেন্স (ফেন্সিং) রঙ করতে হবে K ধরনের রঙ দিয়ে। লক্ষ্য হল খরচ ন্যূনতম রাখা, তবে শর্ত হল কোনো দুটি প্রতিবেশী ফেন্স একই রঙের হতে পারবে না। যদি আমাদের কাছে একটি N x K ম্যাট্রিক্স থাকে যেখানে n-তম সারি এবং k-তম কলাম নম্বর n ফেন্সকে k রঙ দিয়ে রঙ করার খরচ নির্দেশ করে, তবে আমাদের সেই ন্যূনতম খরচ বের করতে হবে।

উদাহরণস্বরূপ, যদি ইনপুট ম্যাট্রিক্স হয়:

তবে আউটপুট হবে 14, কারণ আমরা নিম্নলিখিত রঙের ইনডেক্স বেছে নিতে পারি (প্রথম ফেন্স থেকে শুরু করে): 5 → 2 → 3 → 4।

সমাধানের পদ্ধতি

এই সমস্যাটি সমাধানের জন্য আমরা ডাইনামিক প্রোগ্রামিং ব্যবহার করব, তবে স্পেস অপ্টিমাইজেশন (space optimization) করে। প্রতিটি সারির জন্য শুধু দুটি ন্যূনতম খরচ এবং তাদের সংশ্লিষ্ট রঙের ইনডেক্স ট্র্যাক রাখলেই চলে।

এলগরিদমের ধাপসমূহ:

1. n := ম্যাট্রিক্সের সারি সংখ্যা
2. fc := 0, ft := 0 (প্রথম ন্যূনতম খরচের রঙ ইনডেক্স এবং খরচ)
3. sc := 1, st := 0 (দ্বিতীয় ন্যূনতম খরচের রঙ ইনডেক্স এবং খরচ)
4. প্রতিটি সারি (row) এর জন্য:
   • nfc := -1, nft := infinity (নতুন প্রথম ন্যূনতম)
   • nsc := -1, nst := infinity (নতুন দ্বিতীয় ন্যূনতম)
   • প্রতিটি ইনডেক্স i এবং মান t এর জন্য সারিতে:
     • ct := t + (ft যদি i != fc অন্যথায় st) — বর্তমান খরচ যোগ করুন পূর্বের সারির সেরা খরচের সাথে (একই রঙ এড়িয়ে)।
     • যদি ct <= nft হয়, তবে নতুন প্রথম ও দ্বিতীয় ন্যূনতম আপডেট করুন।
     • অন্যথায় যদি ct <= nst হয়, তবে শুধু নতুন দ্বিতীয় ন্যূনতম আপডেট করুন।
   • fc, ft := nfc, nft এবং sc, st := nsc, nst আপডেট করুন।
5. শেষে ft রিটার্ন করুন।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, matrix):
        n = len(matrix)
        fc, ft = 0, 0
        sc, st = 1, 0
        inf = int(1e18)
        
        for row in matrix:
            nfc, nft = -1, inf
            nsc, nst = -1, inf
            
            for i, t in enumerate(row):
                ct = t + (ft if i != fc else st)
                
                if ct <= nft:
                    nsc, nst = nfc, nft
                    nfc, nft = i, ct
                elif ct <= nst:
                    nsc, nst = i, ct
            
            fc, ft = nfc, nft
            sc, st = nsc, nst
        
        return ft

ob = Solution()
matrix = [
    [6, 4, 5],
    [3, 2, 7],
    [3, 4, 5],
    [5, 4, 4]
]
print(ob.solve(matrix))  # আউটপুট: 14

ইনপুট ও আউটপুট

ইনপুট: [[6, 4, 5], [3, 2, 7], [3, 4, 5], [5, 4, 4]]
আউটপুট: 14