পাইথনে প্রদত্ত দুটি স্থানে সোনা বাছাই করার জন্য সর্বনিম্ন খরচ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি 2d ​​ম্যাট্রিক্স এবং কিছু অন্যান্য মান আছে যেমন row, col, erow0, ecol0, erow1 এবং ecol1। যদি আমাদের বর্তমান অবস্থান ম্যাট্রিক্স [সারি, কল] হয় এবং আমরা ম্যাট্রিক্স [erow0, ecol0] এবং ম্যাট্রিক্স [erow1, ecol1]-এ সোনা নিতে চাই। আমরা উপরে, নিচে, বামে এবং ডানদিকে যেতে পারি কিন্তু যখন আমরা একটি কক্ষে থাকি (r, c), আমাদের খরচ ম্যাট্রিক্স [r, c] দিতে হয়, যদিও আমরা যদি একাধিকবার একটি ঘরে অবতরণ করি তবে আমরা তা করি না আবার সেই সেলের জন্য খরচ দিতে হবে। আমাদের উভয় স্থানে স্বর্ণ সংগ্রহের সর্বনিম্ন খরচ খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট মত হয়

row =0, col =0, erow0 =0, ecol0 =3, erow1 =2, ecol1 =2, তাহলে আউটপুট হবে 8, যেহেতু আমরা (0, 0) এ আছি এবং অবস্থান থেকে সোনা বাছাই করতে চাই (0, 3) এবং (2, 2)। তাই প্রথমে তিন ধাপে (0, 0) থেকে (0, 3) এ যান তারপর (0,0) এ ফিরে আসুন তারপর 1টি চিহ্নিত ঘর অনুসরণ করে (2, 2) এ যান।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন is_valid() সংজ্ঞায়িত করুন। এটি x, y

  লাগবে

• x এবং y ম্যাট্রিক্সের পরিসরে থাকলে true ফেরত দিন, অন্যথায় মিথ্যা

• একটি ফাংশন min_cost() সংজ্ঞায়িত করুন। এটি sx, sy

  লাগবে

• হিপ :=আইটেম সহ একটি গাদা (ম্যাট্রিক্স[sx, sy], sx, sy)

• dists :=প্রদত্ত ম্যাট্রিক্সের একই আকারের একটি ম্যাট্রিক্স এবং inf দিয়ে পূরণ করুন

• dists[sx, sy] :=ম্যাট্রিক্স[sx, sy]

• যখন গাদা খালি না হয়, তখন করুন

  • (খরচ, x, y) :=স্তূপের প্রথম উপাদান এবং স্তূপ থেকে প্রথম উপাদান মুছে ফেলুন

  • প্রতিটি জোড়ার জন্য (nx, ny) [(x, y - 1) ,(x + 1, y) ,(x - 1, y) ,(x, y + 1) ], করুন

    • যদি is_valid(nx, ny) এবং ম্যাট্রিক্স[nx, ny] + খরচ

      • প্রান্ত :=ম্যাট্রিক্স[nx, ny]

      • dists[nx, ny] :=প্রান্ত + খরচ

      • ঢোকান (এজ + খরচ, nx, ny) হিপে

• প্রত্যাবর্তন dists

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• res :=inf

• a :=min_cost(সারি, col), b :=min_cost(erow0, ecol0), c :=min_cost(erow1, ecol1)

• ম্যাট্রিক্সের সারি গণনা 0 থেকে রেঞ্জের জন্য, করুন

  • j রেঞ্জ 0 থেকে ম্যাট্রিক্সের কলাম গণনার জন্য, করুন

    • res :=ন্যূনতম রেস এবং (a[i, j] + b[i, j] + c[i, j] - 2 * ম্যাট্রিক্স[i, j])

• রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

ইমপোর্ট heapqimport ম্যাথক্লাস সমাধান:def solve(self, matrix, row, col, erow0, ecol0, erow1, ecol1):def is_valid(x, y):রিটার্ন x>=0 এবং y>=0 এবং x  
ইনপুট
 <প্রে>[ [1, 1, 1, 1, 1], [1, 10, 10, 10, 10], [1, 1, 1, 10, 10]], 0, 0, 0, 3, 2 , 2

আউটপুট

8