โปรแกรมนับจำนวนการดำเนินการแปลงเมทริกซ์ไบนารีเป็นเมทริกซ์ศูนย์ใน C++

สมมติว่าเรามีเมทริกซ์ไบนารี ตอนนี้พิจารณาการดำเนินการที่เราหยิบเซลล์หนึ่งและพลิกมันและเซลล์ข้างเคียงทั้งหมด (บน, ล่าง, ซ้าย, ขวา) เราต้องหาจำนวนการดำเนินการน้อยที่สุดที่จำเป็นเพื่อให้เมทริกซ์มีแต่ 0 หากไม่มีวิธีแก้ ให้คืนค่า -1

ดังนั้น หากอินพุตเป็นเหมือน

เอาต์พุตจะเป็น 3

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

• กำหนดอาร์เรย์ dir ขนาด 4 x 2 := {{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:
  • ลูป j := 0 ถึง j < c:
    • mask := mask XOR (matrix[i, j] * 2^getPos(i, j))
• กำหนดอาร์เรย์ dist ขนาด 512 และเติม -1
• กำหนดคิว q
• แทรก mask ลง q
• dist[mask] := 0
• while (q ไม่ว่าง):
  • mask := องค์ประกอบแรกของ q
  • ลบองค์ประกอบออกจาก q
  • ลูป i := 0 ถึง i < last:
    • กำหนดคู่ coord
    • x := coord[0]
    • y := coord[1]
    • nmask := mask
    • nmask := nmask XOR 2^i
    • ลูป k := 0 ถึง k < 4:
      • 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 <bits/stdc++.h> 
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<int, int> getCoord(int x){ 
    pair<int, int> ret; 
    ret.first = x / c; 
    ret.second = x % c; 
    return ret; 
} 

int solve(vector<vector<int>>& 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<int> dist(1 << 9, -1); 
    queue<int> q; 
    q.push(mask); 
    dist[mask] = 0; 
    while(!q.empty()){ 
        mask = q.front(); 
        q.pop(); 
        for(int i = 0; i < last; i++){ 
            pair<int, int> 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<vector<int>> v = {{0, 0}, {1, 0}}; 
    cout << solve(v); 
}

อินพุต

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

เอาต์พุต

3