จำนวนการพลิกขั้นต่ำเพื่อแปลงเมทริกซ์ไบนารีเป็นเมทริกซ์ศูนย์ใน C++

สมมติว่าเรามีเสื่อเมทริกซ์ไบนารีขนาด m x n ในขั้นตอนเดียว เราสามารถเลือกเซลล์หนึ่งเซลล์แล้วพลิกบิตและเซลล์เพื่อนบ้านทั้งสี่เซลล์หากมีอยู่ เราต้องหาจำนวนขั้นตอนขั้นต่ำที่จำเป็นในการแปลง mat เป็นเมทริกซ์ศูนย์ หากไม่มีวิธีแก้ปัญหา ให้คืนค่า -1

ดังนั้นหากอินพุตที่กำหนดเป็น [[0,0], [0,1]] การเปลี่ยนแปลงจะเป็นเช่น −

ดังนั้นเราต้องการ 3 ขั้นตอน ผลลัพธ์จะเป็น 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=จำนวนแถว, m :=จำนวนคอลัมน์, x :=0
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• สำหรับการเริ่มต้น j :=0 เมื่อ j
• สำหรับการเริ่มต้น j :=0 เมื่อ j
• x :=x + left shift mat[i][j] value (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