C++ এ বাইনারি ম্যাট্রিক্সকে শূন্য ম্যাট্রিক্সে রূপান্তর করতে অপারেশনের সংখ্যা গণনা করার প্রোগ্রাম

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

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

0	0
1	0

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

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

আকারের একটি অ্যারে ডির সংজ্ঞায়িত করুন:4 x 2 :={{1, 0}, {0, 1}, { - 1, 0}, {0, - 1}}
const int inf =10^6
একটি ফাংশন getPos() সংজ্ঞায়িত করুন, এতে i, j,
রিটার্ন i * c + j
একটি ফাংশন সংজ্ঞায়িত করুন getCoord() এতে x
- এক জোড়া ret সংজ্ঞায়িত করুন
- ret[0] :=x / c
- ret[1] :=x mod c
- রিটার্ন রিটার্ন
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
মাস্ক :=0
r :=ম্যাট্রিক্সের সারি গণনা
c :=ম্যাট্রিক্সের কলাম সংখ্যা
শেষ :=r * c
আরম্ভ করার জন্য i :=0, যখন i
আরম্ভ করার জন্য j :=0, যখন j
মাস্ক :=মাস্ক XOR (ম্যাট্রিক্স[i, j] * 2^getPos(i, j))

512 আকারের একটি অ্যারে ডিস্ট সংজ্ঞায়িত করুন এবং -1 দিয়ে পূরণ করুন

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

q এ মাস্ক ঢোকান

dist[মাস্ক] :=0

যখন (q খালি নয়), করবেন:

মাস্ক :=q এর প্রথম উপাদান
q থেকে উপাদান মুছুন
আরম্ভ করার জন্য i :=0, যখন i <শেষ, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), করুন:
- এক জোড়া কর্ড সংজ্ঞায়িত করুন
- x :=coord[0]
- y :=coord[1]
- nmask :=মুখোশ
- nmask :=nmask XOR 2^i
- আরম্ভ করার জন্য k :=0, যখন k <4, আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), করুন:
  - nx :=x + dir[k, 0]
  - ny :=y + dir[k, 1]
  - যদি nx এবং ny ম্যাট্রিক্সের পরিসরে না হয়, তাহলে:
    - নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
  - pos :=getPos(nx, ny)
  - nmask :=nmask XOR (2^pos)
- যদি dist[nmask] -1 বা dist[nmask]> dist[mask] + 1 এর মত হয়, তাহলে:
  - dist[nmask] :=dist[mask] + 1
  - q-এ nmask ঢোকান

রিটার্ন ডিস্ট[0]

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

উদাহরণ

#include
using namespace std;
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int c;
int r;
int last;
const int inf = 1e6;

int getPos(int i, int j){
   return i * c + j;
}
pair getCoord(int x){
   pair ret;
   ret.first = x / c;
   ret.second = x % c;
   return ret;
}

int solve(vector>& matrix) {
   int mask = 0;
   r = matrix.size();
   c = r ? matrix[0].size() : 0;
   last = r * c;
   for(int i = 0; i < r; i++){
      for(int j = 0; j < c; j++){
         mask ^= (matrix[i][j] << getPos(i, j));
      }
   }
   vector dist(1 << 9, -1);
   queue q;
   q.push(mask);
   dist[mask] = 0;
   while(!q.empty()){
      mask = q.front();
      q.pop();
     
      for(int i = 0; i < last; i++){
         pair coord = getCoord(i);      
         int x = coord.first;
         int y = coord.second;
         
         int nmask = mask ;
         nmask ^= (1 << i);
         for(int k = 0; k < 4; k++){
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];
            if(nx < 0 || nx >= r || ny < 0 || ny >= c)
               continue;
            int pos = getPos(nx, ny);
            nmask ^= (1 << pos);
         }
         
         if(dist[nmask] == -1 || dist[nmask] > dist[mask] + 1){
            dist[nmask] = dist[mask] + 1;
            q.push(nmask);
         }
      }
   }
   return dist[0];
}
int main(){
   vector> v = {{0, 0},{1, 0}};
   cout << solve(v);
}

ইনপুট

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