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

ภาพรวมปัญหา

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

ตัวอย่าง

ถ้าอินพุตคือ [[0,0], [0,1]] การเปลี่ยนแปลงจะเป็นดังนี้:

เราต้องใช้ 3 ขั้นตอน ดังนั้นผลลัพธ์คือ 3

แนวทางแก้ปัญหา

เราจะทำตามขั้นตอนดังนี้:

• n := จำนวนแถว, m := จำนวนคอลัมน์, x := 0
• แปลงเมทริกซ์เป็นตัวเลขบิต (bitmask) โดยเก็บค่าในตัวแปร x
• สร้างอาร์เรย์ dp ขนาด 2^(n*m) เติมด้วย -1
• dp[x] := 0 และนำ x เข้า queue
• ทำ BFS: ดึงสถานะปัจจุบันจาก queue ถ้าเป็น 0 คืนค่า dp[current]
• ลองกลับบิตที่ทุกตำแหน่ง (i,j) และเพื่อนบ้าน 4 ทิศทาง สร้างสถานะใหม่ temp
• ถ้า dp[temp] == -1 ให้อัปเดต dp[temp] = dp[current] + 1 และ push เข้า queue
• ถ้า queue ว่างแล้วไม่เจอคำตอบ ให้คืนค่า -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;
    }
};

int main(){
    Solution ob;
    vector<vector<int>> v = {{0,0},{0,1}};
    cout << (ob.minFlips(v));
}

Input

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

Output

3