পাইথনে গোলকধাঁধা ম্যাট্রিক্স থেকে বাঁচতে ন্যূনতম সংখ্যা

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে, যেখানে 0 একটি খালি ঘরের প্রতিনিধিত্ব করছে এবং 1 হল একটি প্রাচীর। যদি আমরা উপরের বাম কোণ থেকে শুরু করি (0, 0), তাহলে নিচের ডানদিকের কোণায় যেতে ন্যূনতম কতগুলি ঘর লাগবে তা খুঁজে বের করতে হবে (R-1, C-1) এখানে R হল সারির সংখ্যা এবং C হল সংখ্যা। কলামের যদি আমরা কোন উত্তর খুঁজে না পাই, ফিরে আসুন -1.

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

তাহলে আউটপুট হবে 8 কারণ, আমরা −

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

• R :=সারির সংখ্যা
• C :=কলামের সংখ্যা
• q :=একটি খালি তালিকা, প্রাথমিকভাবে সন্নিবেশ করান (0, 0, 1) যদি ম্যাট্রিক্স[0, 0] 0 ​​হয়
• ম্যাট্রিক্স[0, 0] :=1
• প্রতিটি ট্রিপলেটের জন্য (r, c, d) q, do
  • যদি (r, c) একই হয় (R - 1, C - 1), তাহলে
    • রিটার্ন d
  • প্রতিটি x, y এর জন্য [(r + 1, c) ,(r - 1, c) ,(r, c + 1) ,(r, c - 1) ], do
    • যদি 0 <=x
    • ম্যাট্রিক্স[x, y] :=1
    • q এর শেষে ট্রিপলেট (x, y, d + 1) ঢোকান

উদাহরণ

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

def solve(matrix):R, C =len(matrix), len(matrix[0]) q =[(0, 0, 1)] যদি ম্যাট্রিক্স না হয় [0][0] অন্য [] ম্যাট্রিক্স[ 0][0] =1 এর জন্য r, c, d in q:if (r, c) ==(R - 1, C - 1):x, y এর জন্য d [(r + 1, c), রিটার্ন করুন (r - 1, c), (r, c + 1), (r, c - 1)]:যদি 0 <=x  
ইনপুট
 <প্রে>[[0, 0, 0, 1, 0], [0, 0, 1, 1, 0], [0, 0, 0, 1, 1], [1, 1, 0, 0, 0] ]]

আউটপুট

8