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

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

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

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

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

n := पंक्तियों की संख्या, m := स्तंभों की संख्या, x := 0
i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
- j := 0 से प्रारंभ करें, जब j < m, j बढ़ाते हुए, करें -
  - j := 0 से प्रारंभ करें, जब j < m, j बढ़ाते हुए, करें -
    - x := x + mat[i][j] मान को (i * m) + j बार बाएं शिफ्ट करें
2^(n * m) सेल वाला एक ऐरे dp परिभाषित करें, इसे -1 से भरें
dp[x] := 0
एक क्यू q परिभाषित करें
x को q में डालें
जब (q खाली नहीं है), करें -
current := q का पहला तत्व, q से तत्व हटाएं
यदि current 0 के समान है, तो -
- dp[current] वापस करें
i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
- j := 0 से प्रारंभ करें, जब j < m, j बढ़ाते हुए, करें -
  - temp := current
  - temp := temp XOR 2^ (i * m) + j)
  - k := 0 से प्रारंभ करें, जब k < 4, k बढ़ाते हुए, करें -
    - ni := i + dir[k][0]
    - nj := j + dir[k][1]
    - यदि ni < 0 या nj < 0 या ni >= n या nj >= m, तो -
      - अगले भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
      - 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}}