সি++-এ বাইনারি ম্যাট্রিক্সকে শূন্য ম্যাট্রিক্সে রূপান্তর করার জন্য ন্যূনতম ফ্লিপ সংখ্যা

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

যেমন, ইনপুট [[0,0], [0,1]] হলে, পরিবর্তন হবে নিচের ছবির মতঃ

এখানে ৩টি ধাপ লাগবে, তাই আউটপুট হবে ৩।

সমাধানের ধাপসমূহ

n := সারি সংখ্যা, m := কলাম সংখ্যা, x := 0
i := 0 থেকে n-1 পর্যন্ত লুপ চালাতে হবে
- j := 0 থেকে m-1 পর্যন্ত লুপ চালাতে হবে
  - x := x + (mat[i][j] << ((i * m) + j))
২^(n*m) আকারের একটি dp অ্যারে সংজ্ঞায়িত করুন, -1 দিয়ে ভরুন
dp[x] := 0
একটি কিউ q সংজ্ঞায়িত করুন
x কে q-তে ঢুকান
যখন q খালি নয়, তখন লুপ চালান
- current := q-এর প্রথম উপাদান, q থেকে মুছে ফেলুন
- যদি current ০ এর সমান হয়, তবে dp[current] রিটার্ন করুন
- প্রতিটি সেল (i, j) এর জন্য
  - temp := current
  - temp := temp XOR 2^((i * m) + j)
  - চারটি দিকের প্রতিবেশী সেলের জন্য
    - ni := i + dir[k][0], nj := j + dir[k][1]
    - যদি ni বা nj অবৈধ হয়, তবে পরবর্তী ইটারেশনে যান
    - temp := temp XOR 2^((ni * m) + nj)
  - যদি dp[temp] == -1 হয়, তবে
    - dp[temp] := dp[current] + 1
    - temp কে q-তে ঢুকান
-1 রিটার্ন করুন

উদাহরণ

#include <bits/stdc++.h> using namespace std; int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}; class Solution { public:    int minFlips(vector<vector<int>>& mat) {       int n = mat.size();       int m = mat[0].size();       int x = 0;       for(int i = 0; i < n; i++){          for(int j = 0; j < m; j++){             x += (mat[i][j] << ((i * m) + j));          }       }       vector < int > dp(1 << (n*m), -1);       dp[x] = 0;       queue <int> q;       q.push(x);       while(!q.empty()){          int current = q.front();          q.pop();          if(current == 0)return dp[current];          for(int i = 0; i < n; i++){             for(int j = 0; j < m; j++){                int temp = current;                temp ^= (1 << ((i *m) + j));                for(int k = 0; k < 4; k++){                   int ni = i + dir[k][0];                   int nj = j + dir[k][1];                   if(ni < 0 || nj < 0 || ni >= n || nj >= m)continue;                   temp ^= (1 << ((ni *m) + nj));                }                if(dp[temp] == -1){                   dp[temp] = dp[current] + 1;                   q.push(temp);                }             }          }       }       return -1;    } }; main(){    Solution ob;    vector<vector<int>> v = {{0,0},{0,1}};    cout << (ob.minFlips(v)); }

ইনপুট

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