सी ++ में बाइनरी मैट्रिक्स को शून्य मैट्रिक्स में बदलने के लिए संचालन की संख्या की गणना करने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है। अब एक ऑपरेशन पर विचार करें जहां हम एक सेल लेते हैं और इसे और उसके सभी पड़ोसी कोशिकाओं (ऊपर, नीचे, बाएं, दाएं) को फ्लिप करते हैं। हमें आवश्यक संक्रियाओं की न्यूनतम संख्या ज्ञात करनी होगी जैसे कि मैट्रिक्स में केवल 0s हों। अगर कोई समाधान नहीं है, तो -1 लौटें।

तो, अगर इनपुट पसंद है

तो आउटपुट 3 होगा।

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

• आकार की एक सरणी dir परिभाषित करें:4 x 2 :={{1, 0}, {0, 1}, { - 1, 0}, {0, - 1}}
• const int inf =10^6
• एक फ़ंक्शन को परिभाषित करें getPos(), इसमें i, j,
लगेगा
• रिटर्न आई * सी + जे
• एक फ़ंक्शन को परिभाषित करें getCoord () इसमें x लगेगा
  • एक जोड़ी रिट परिभाषित करें
  • 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))

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

उदाहरण

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

आउटपुट

3