C++ में बाइनरी मैट्रिक्स को ज़ीरो मैट्रिक्स में बदलने के लिए फ़्लिप की न्यूनतम संख्या

मान लीजिए हमारे पास एक m x n बाइनरी मैट्रिक्स मैट है। एक चरण में, हम एक सेल चुन सकते हैं और उसके बिट को फ्लिप कर सकते हैं और यदि वे मौजूद हैं तो उसके चारों पड़ोसी। हमें मैट को शून्य मैट्रिक्स में बदलने के लिए आवश्यक न्यूनतम चरणों की संख्या ज्ञात करनी होगी। अगर कोई समाधान नहीं है, तो -1 लौटें।

इसलिए यदि दिया गया इनपुट [[0,0], [0,1]] जैसा है, तो परिवर्तन इस तरह होगा -

तो हमें 3 चरणों की आवश्यकता है, आउटपुट 3 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=पंक्तियों की संख्या, m :=स्तंभों की संख्या, x :=0
• इनिशियलाइज़ i :=0 के लिए, जब i करें
• इनिशियलाइज़ j :=0 के लिए, जब j करें
• इनिशियलाइज़ j :=0 के लिए, जब j करें
• x :=x + लेफ्ट शिफ्ट मैट[i][j] मान (i * m) + j) कई बार

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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}}

आउटपुट

3