C++ এ 01 ম্যাট্রিক্স

ধরুন আমাদের একটি ম্যাট্রিক্স 0 এবং 1 নিয়ে গঠিত, আমাদের প্রতিটি ঘরের জন্য নিকটতম 0 এর দূরত্ব বের করতে হবে। এখানে দুটি সংলগ্ন কক্ষের মধ্যে দূরত্ব হল 1.

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

তাহলে আউটপুট হবে

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

• আকারের একটি অ্যারে ডির সংজ্ঞায়িত করুন:4 x 2 :={{1, 0}, { - 1, 0}, {0, - 1}, {0, 1}}

• n :=সারি গণনা, m :=কলাম গণনা

• একটি ম্যাট্রিক্স রেট অফ অর্ডার (n x m) সংজ্ঞায়িত করুন এবং এটি inf দিয়ে পূরণ করুন

• একটি সারি q

  সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • j শুরু করার জন্য :=0, যখন j করুন

    • যদি ম্যাট্রিক্স[i, j] অ-শূন্য না হয়, তাহলে −

      • ret[i, j] :=0

      • q

        -এ {i, j} সন্নিবেশ করান

• lvl শুরু করার জন্য :=1, যখন q খালি না থাকে, আপডেট করুন (lvl 1 দ্বারা বাড়ান), করুন −

  • sz :=q এর আকার

  • যখন sz অ-শূন্য হয়, প্রতিটি পুনরাবৃত্তিতে 1 দ্বারা sz কমান, −

    • এক জোড়া curr সংজ্ঞায়িত করুন :=q এর সামনের উপাদান

    • q

      থেকে উপাদান মুছুন

    • আরম্ভ করার জন্য k :=0, যখন k <4, আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), করুন −

      • nx :=curr.first + dir[k, 0]

      • ny :=curr.second + dir[k, 1]

      • যদি nx <0 বা nx>=n বা ny <0 বা ny>=m বা ret[nx, ny]

        • ret[nx, ny] :=lvl

      • q

        -এ {nx, ny} ঢোকান

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

উদাহরণ

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

#include  namespace ব্যবহার করে std;void print_vector(vector> v){ cout <<"["; for(int i =0; i> আপডেটম্যাট্রিক্স(ভেক্টর<ভেক্টর>এন্ড ম্যাট্রিক্স) { int n =matrix.size(); int m =matrix[0].size(); ভেক্টর <ভেক্টর > ret(n, ভেক্টর (m, INT_MAX)); সারি <জোড়া > q; for(int i =0; i  curr =q.front(); q.pop(); for(int k =0; k <4; k++){ int nx =curr.first + dir[k][0]; int ny =curr.second + dir[k][1]; যদি(nx <0 || nx>=n || ny <0 || ny>=m || ret[nx][ny] > v ={{0,0,0},{0,1,0},{1,1,1}}; print_vector(ob.updateMatrix(v));}

ইনপুট

{0,0,0},{0,1,0},{1,1,1}}

আউটপুট