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

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

तो, यदि इनपुट इस तरह है

0	0
1	0

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

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

आकार 4 x 2 का एक सरणी dir परिभाषित करें := {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
const int inf = 10^6
एक फ़ंक्शन getPos() परिभाषित करें, यह i, j लेगा,
i * c + j वापस करें
एक फ़ंक्शन getCoord() परिभाषित करें यह x लेगा
- एक युग्म ret परिभाषित करें
- ret[0] := x / c
- ret[1] := x mod c
- ret वापस करें
मुख्य विधि से निम्नलिखित करें:
mask := 0
r := मैट्रिक्स की पंक्ति संख्या
c := मैट्रिक्स की कॉलम संख्या
last := r * c
i := 0 से शुरू करें, जब i < r, अपडेट करें (i को 1 से बढ़ाएं), करें:
- j := 0 से शुरू करें, जब j < c, अपडेट करें (j को 1 से बढ़ाएं), करें:
  - mask := mask XOR (matrix[i, j] * 2^getPos(i, j))
आकार 512 का एक सरणी dist परिभाषित करें और -1 से भरें
एक क्यू q परिभाषित करें
mask को q में डालें
dist[mask] := 0
जब (q खाली नहीं है), करें:
- mask := q का पहला तत्व
- q से तत्व हटाएं
- i := 0 से शुरू करें, जब i < last, अपडेट करें (i को 1 से बढ़ाएं), करें:
  - एक युग्म coord परिभाषित करें
  - x := coord[0]
  - y := coord[1]
  - nmask := mask
  - nmask := nmask XOR 2^i
  - k := 0 से शुरू करें, जब k < 4, अपडेट करें (k को 1 से बढ़ाएं), करें:
    - nx := x + dir[k, 0]
    - ny := y + dir[k, 1]
    - यदि nx और ny मैट्रिक्स की रेंज में नहीं हैं, तो:
      - निम्न भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
    - pos := getPos(nx, ny)
    - nmask := nmask XOR (2^pos)
  - यदि dist[nmask] -1 के समान है या dist[nmask] > dist[mask] + 1, तो:
    - dist[nmask] := dist[mask] + 1
    - nmask को q में डालें
dist[0] वापस करें

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

उदाहरण

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